#include #include #include using namespace std; #define MAX_V 2001 #define FOR(t,i,n) for(t i=0;i _vector_long; _vector_long adj[MAX_V]; //Adjacency vector representation of graph _vector_long adj_t[MAX_V]; //Adjacency vector representation of transpose of graph long order[MAX_V], finish[MAX_V], scc_number[MAX_V]; long t_time, scc_num; char color[MAX_V]; char scc_in[MAX_V]; //1 if there are outgoing vertices from this SCC long V, E; int compare(const void *a, const void *b) { long aa = *(long *)a; long bb = *(long *)b; return finish[bb]-finish[aa]; } void DFS_visit(_vector_long adj[], long u) { scc_number[u]=scc_num; color[u]=0; t_time++; FIT(_vector_long,i,adj[u]) { if(color[*i]==1) { DFS_visit(adj, *i); } } finish[u]=t_time=t_time+1; } long DFS(_vector_long adj[]) { long count=0; //Keeps a count of the number of DFS forests scc_num=0; t_time=0; FOR(long,i,V) color[i]=1; //1 --> NOT VISITED, 0 --> VISITED FOR(long,i,V) { if(color[order[i]]==1) { count++; DFS_visit(adj, order[i]); scc_num++; } } return count; } int main() { scanf("%ld %ld", &V, &E); FOR(long,i,E) { long f, t; scanf("%ld %ld", &f, &t); adj[f-1].push_back(t-1); adj_t[t-1].push_back(f-1); } //Compute the number of strongly connected components FOR(long, i, V) order[i]=i; //Initial order for DFS, numerical //Compute the finish times DFS(adj); //Reorder order according to finish qsort(order, V, sizeof(long), compare); long count=DFS(adj_t); //memset(scc_in, 0, sizeof(scc_in)); --- scc_in made global FOR(long,i,V) FIT(_vector_long,j,adj[i]) { if(scc_number[i]!=scc_number[*j]) { scc_in[scc_number[*j]]=1; } } long ans=0; FOR(long,i,count) ans+=scc_in[i]; count-=ans; printf("%ld\n", count); return 0; }