Pagini recente » Cod sursa (job #752667) | Cod sursa (job #365645) | Cod sursa (job #2494083) | Cod sursa (job #2387958) | Cod sursa (job #2112124)
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;
vector<int>G[MAX_N + 1], scc[MAX_N + 1];
int d[MAX_N + 1], st[MAX_N + 1], n, m, numScc, vf;
bool onStack[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);
}
fclose(fin);
}
int DFS(int node, int depth) {
d[node] = depth;
st[++vf] = node;
onStack[node] = true;
for(vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++) {
if(!d[*it]) {
d[node] = min(d[node],DFS(*it, depth + 1));
} else if(onStack[*it]) {
d[node] = min(d[node], d[*it]);
}
}
if(d[node] == depth) {
while(st[vf] != node) {
scc[numScc].push_back(st[vf]);
onStack[st[vf]] = false;
vf--;
}
scc[numScc++].push_back(st[vf]);
onStack[st[vf]] = false;
vf--;
}
return d[node];
}
void DFS_Master() {
int depth;
for(int i = 1; i <= n; i++) {
if(!d[i]) {
depth = 1;
d[i] = DFS(i,depth);
}
}
}
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();
DFS_Master();
printSCC();
return 0;
}