Pagini recente » Cod sursa (job #1797131) | Cod sursa (job #919161) | Cod sursa (job #1174954) | Cod sursa (job #1658412) | Cod sursa (job #2112123)
#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 st[MAX_N + 1], n, m, numScc, vf;
bool used[MAX_N + 1];
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 node) {
vector<int>::iterator it;
used[node] = true;
for(it = G[node].begin(); it != G[node].end(); it++) {
if(!used[*it])
DFS(*it);
}
st[vf++] = node;
}
void DFS_master() {
for(int i = 1; i <= n; i++)
if(!used[i])
DFS(i);
}
void DFS_reverseGraph(int node) {
vector<int>::iterator it;
used[node] = true;
scc[numScc].push_back(node);
for(it = Gt[node].begin(); it != Gt[node].end(); it++) {
if(!used[*it])
DFS_reverseGraph(*it);
}
}
void Kosaraju() {
DFS_master();
for(int i = 1; i <= n; i++)
used[i] = false;
for(int i = vf - 1; i >= 0; i--) {
if(!used[st[i]]) {
DFS_reverseGraph(st[i]);
numScc++;
}
}
}
void printSCC() {
FILE *fout = fopen("ctc.out","w");
fprintf(fout,"%d\n",numScc);
for(int i = 0; i < numScc; i++) {
for(vector<int>::iterator it = scc[i].begin(); it != scc[i].end(); it++)
fprintf(fout,"%d ",*it);
fprintf(fout,"\n");
}
fclose(fout);
}
int main() {
readGraph();
Kosaraju();
printSCC();
return 0;
}