First, I find all the connected components and then I see if a connected component affects another one, then I only take the connected components which aren't affected by any other connceceted component.
Code: Select all
#include<iostream>
#include<vector>
using namespace std;
vector< vector<int> > L1;
vector< vector<int> > L2;
vector<int> v;
bool visited[100000];
int component[100000];
int num_components;
bool in_component[100000];
void dfs1(int start){
visited[start]=true;
for(int i=0;i<L1[start].size();i++)
if(!visited[L1[start][i]])
dfs1(L1[start][i]);
v.push_back(start);
}
void dfs2(int start){
visited[start]=true;
component[start]=num_components;
for(int i=0;i<L2[start].size();i++)
if(!visited[L2[start][i]])
dfs2(L2[start][i]);
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T,n,m,a,b,cont;
scanf("%d",&T);
for(int caso=0;caso<T;caso++){
scanf("%d %d",&n,&m);
L1.clear();
L1.resize(n);
L2.clear();
L2.resize(n);
for(int i=0;i<m;i++){
scanf("%d %d",&a,&b);
L1[a-1].push_back(b-1);
L2[b-1].push_back(a-1);
}
fill(visited,visited+n,false);
v.clear();
for(int i=0;i<n;i++){
if(!visited[i]){
dfs1(i);
}
}
fill(visited,visited+n,false);
num_components=0;
for(int i=v.size()-1;i>=0;i--){
if(!visited[v[i]]){
dfs2(v[i]);
num_components++;
}
}
fill(in_component,in_component+num_components,false);
for(int i=0;i<n;i++)
for(int j=0;j<L1[i].size();j++)
if(component[i]!=component[L1[i][j]])
in_component[component[L1[i][j]]]=true;
cont=0;
for(int i=0;i<num_components;i++)
if(!in_component[i]) cont++;
cout<<cont<<endl;
}
return 0;
}