Pagini recente » Cod sursa (job #589720) | Cod sursa (job #2579178) | Cod sursa (job #2597342) | Cod sursa (job #1307861) | Cod sursa (job #2210409)
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;
vector<int>g[MAX_N+1], gt[MAX_N+1], scc[MAX_N+1];
int f[MAX_N+1], n, m, numSCC, k;
bool used[MAX_N+1];
void readGraph() {
int i, x, y;
FILE* fin = fopen("ctc.in","r");
fscanf(fin,"%d%d",&n,&m);
for(i = 0; i < m; i++) {
fscanf(fin,"%d%d",&x,&y);
g[x].push_back(y);
gt[y].push_back(x);
}
fclose(fin);
}
void DFS(int node) {
used[node] = true;
for(auto i : g[node])
if(!used[i])
DFS(i);
f[k++] = node;
}
void DFS_master() {
for(int i = 1; i <= n; i++)
if(!used[i])
DFS(i);
}
void DFSreverseGraph(int node) {
used[node] = true;
scc[numSCC].push_back(node);
for(auto i : gt[node])
if(!used[i])
DFSreverseGraph(i);
}
void Kosaraju() {
int i;
for(i = 1; i <= n; i++)
used[i] = false;
for(i = n-1; i >= 0; i--) {
if(!used[f[i]]) {
DFSreverseGraph(f[i]);
numSCC++;
}
}
}
void printSCC() {
FILE* fout = fopen("ctc.out","w");
fprintf(fout,"%d\n",numSCC);
for(int i = 0; i < numSCC; i++) {
for(int j = 0; j < scc[i].size(); j++)
fprintf(fout,"%d ",scc[i][j]);
fprintf(fout,"\n");
}
fclose(fout);
}
int main() {
readGraph();
DFS_master();
Kosaraju();
printSCC();
return 0;
}