문제

도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다.

이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하자.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 도미노 블록의 번호는 1과 N 사이의 정수다. 다음 M개의 줄에는 각각 두 정수 x, y가 주어지는데, 이는 x번 블록이 넘어지면 y번 블록도 넘어짐을 뜻한다.

출력

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 정답은 손으로 넘어뜨려야 하는 최소의 도미노 블록 개수이다.

https://www.acmicpc.net/problem/4196

풀이

한번 건드리면 함꼐 무너지는 연결된 도미노 관계가 문제에서 주어진다.
따라서 어느 한 도미노를 넘어뜨렸을때 그 도미노를 통해 이동가능한 모든 도미노가 한번에 넘어지므로, 사실상 DFS만으로도 문제를 풀 수 있으나 SCC알고리즘을 배운 참에 써보기로했다.

다만 일반적인 SCC알고리즘으로 찾은 SCC갯수만을 출력하면 틀린다.
왜냐면 하나의 SCC가 다른 SCC를 가리키는 경우가 있기 때문이다.

아래와 같은 그래프(도미노간의 연결상태)가 있다고 치자.

다른 SCC도 함께 넘어져야하는것이다. 따라서 이경우 최소한으로 넘어뜨려야할 횟수는 1회인것이다. SCC의갯수인 4가 아니다.

따라서 이런 SCC간의 연결됨을 체킹해주기위해 아래와 같은 과정을 거쳐야한다.

• 각 정점마다 자신이 속한 SCC의 번호를 매겨준다.
• 모든 그래프간의 두 정점 u -> v 에서 u 와 v가 서로 다른 SCC에 속한다면(1번 이용) v번째 SCC로의 접근이 있는 상태인것.
• 따라서 inDegree[v] = true로 체크해주자
• 결과적으로 inDegree[i] = false인 갯수를 세어 출력하면된다.

이제 구현을 해보자.

1. 필요한 요소들
   SCC에 필요한 요소들이나, 마지막에 group과 indegree가 추가되었다.
   
   
   
2. SCC 코드 (DFS부분)
   120번줄에 group설정하는 코드는 각 정점마다 몇번 SCC에 속하는지 체크해주어
   이후에 서로다른 SCC에 속하는지 판별할때 사용한다.
   이것만이 기존의 DFS코드와의 차이점이다.
   
   
   
3. inDegree를 작성하는 부분
   154~155에서 SCC를 실행해주고,
   그래프의 모든 요소간의 연결된 두 정점 u, v를 체크하여,
   두 정점이 서로다른 SCC에 속한다면,
   목적지인 정점 v가 속하는 SCC가 다른 SCC로부터의 접근을 허용하고 있다는것이다.
   따라서 inDegree[v] = true로 체크해준다.
   마지막으로 inDegree[i] == false인 갯수를 세어 출력해주면 끝난다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define emp() empty()
#define len(x) x.length()
#define sz(x) ((int)x.size()) //컨테이너에서 사용
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
#define MAX 100001
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill; _UG std::stoi; _UG std::stod; _UG std::stof; _UG std::stol; _UG std::stold; _UG std::stoll; _UG std::stoul; _UG std::stoull;
_UG std::min; //_UG std::map;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

int T;
int N, M, id;
int P[MAX];
bool visited[MAX];
vi arr[MAX];
si S;
vector<vi> scc;
int group[MAX]; //각각정점이 몇번 SCC에 속하는지 체킹
bool inDegree[MAX]; //각각SCC의 번호마다 다른 SCC에서의 접근이 가능한지 체킹(기본값 false)

void init();
int SCC(int x, int& id, int(&P)[MAX], bool(&visited)[MAX], vi(&arr)[MAX], si& S);
void func();

void init() {
	sc("%d", &T);
}

int SCC(int x, int &id, int (&P)[MAX], bool (&visited)[MAX], 
	vi (&arr)[MAX], si &S) {
	P[x] = ++id;
	S.ph(x);

	int parent = P[x];
	rep(i, sz(arr[x])) {
		int y = arr[x][i];
		if (P[y] == 0)
			parent = min(parent, SCC(y, id, P, visited, arr, S)); //사실상 P[y]를 구하기윟 SCC(y) 호출
		else if (!visited[y])
			parent = min(parent, P[y]); //이미 구해진값P[y] 사용
	}

	if (parent == P[x]) {
		vi list;
		while (x) {
			int y = S.TT();
			S.PP();
			group[y] = sz(scc) + 1; //각 정점이 몇번 SCC에 속해있는지 숫자를매김
			visited[y] = true;
			list.pb(y);
			if (y == x) br;
		}
		scc.pb(list);
	}

	return parent;
}

//프로그램 메인 로직
void func() {
	rep(_, T) {
		sc("%d%d", &N, &M);

		//각 요소들 초기화
		id = 0;
		ms(P);
		ms(visited);
		ms(group);
		ms(inDegree);
		msv(scc); 
		rep(i, N + 1)
			arr[i].cls();

		//연결정보를 입력받음
		rep(__, M) {
			int x, y;
			sc("%d%d", &x, &y);
			arr[x].pb(y); //x->y 연결
		}

		//방문하지 않은 정점을 모두 DFS적용하여 총 SCC그룹갯수인 res를 구함
		rrep(i, 1, N + 1) 
			if (P[i] == 0) SCC(i, id, P, visited, arr, S);

		//그래프의 모든 정점마다 연결된 모든 정점을 탐색하여
		//연결된 두 정점 u -> v가 서로 다른 SCC에 존재하면
		//v번 SCC가 inDegree가 있는 SCC인것이다.
		//따라서 inDegree[v] 를 체크해주자.
		rrep(i, 1, N + 1) {
			rep(j, sz(arr[i])) {
				int y = arr[i][j];
				if (group[i] != group[y])
					//다른 SCC에서 현재 정점이 속한 SCC로 접근이 가능하다. 
					// -> 도미노가 연달아 쓰러짐
					inDegree[group[y]] = true; 
			}
		}

		int res = 0;
		rrep(i, 1, sz(scc) + 1)
			if (!inDegree[i])
				res++; //고립된 SCC만 체크

		pr("%d\n", res);
	}


}

int main(void) {
	init();
	func();

	rt 0;
}