Pagini recente » Cod sursa (job #2626761) | Cod sursa (job #2049287) | Cod sursa (job #1907915) | Cod sursa (job #2433096) | Cod sursa (job #2228485)
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;
vector<int>g[MAX_N+1], gt[MAX_N+1], scc[MAX_N];
bool used[MAX_N+1];
int st[MAX_N], head;
int n, m, numSCC;
void readGraph() {
int x, y;
FILE* fin = fopen("ctc.in","r");
fscanf(fin,"%d%d",&n,&m);
for(int 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 x) {
used[x] = true;
for(auto i : g[x])
if(!used[i])
DFS(i);
st[head++] = x;
}
void DFS_master() {
for(int i = 1; i <= n; i++)
if(!used[i])
DFS(i);
}
void DFSreverseGraph(int x) {
scc[numSCC].push_back(x);
used[x] = true;
for(auto i : gt[x])
if(!used[i])
DFSreverseGraph(i);
}
void Kosaraju() {
int i;
DFS_master();
for(i = 1; i <= n; i++)
used[i] = 0;
for(i = head - 1; i >= 0; i--) {
if(!used[st[i]]) {
DFSreverseGraph(st[i]);
++numSCC;
}
}
}
void printSCC() {
int i;
FILE* fout = fopen("ctc.out","w");
fprintf(fout,"%d\n",numSCC);
for(i = 0; i < numSCC; i++) {
for(auto j : scc[i])
fprintf(fout,"%d ",j);
fprintf(fout,"\n");
}
fclose(fout);
}
int main() {
readGraph();
Kosaraju();
printSCC();
return 0;
}