Pagini recente » Cod sursa (job #1155954) | Cod sursa (job #2138318) | Cod sursa (job #941502) | Cod sursa (job #1258020) | Cod sursa (job #2112245)
#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], viz[MAX_N + 1], st[MAX_N + 1], n, m, numScc, vf, k;
bool used[MAX_N + 1];
inline int minim(int x, int y) {
if(x <= y) return x;
return y;
}
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);
}
void DFS(int node) {
st[++vf] = node;
used[node] = true;
d[node] = viz[node] = ++k;
for(vector<int>::iterator it = g[node].begin(); it != g[node].end(); it++) {
if(!d[*it]) {
DFS(*it);
d[node] = minim(d[node],d[*it]);
} else if(used[*it]) {
d[node] = minim(d[node],d[*it]);
}
}
if(d[node] == viz[node]) {
do {
scc[numScc].push_back(st[vf]);
used[st[vf]] = false;
vf--;
}while(st[vf + 1] != node);
numScc++;
}
}
void DFS_master() {
for(int i = 1; i <= n; i++)
if(!viz[i])
DFS(i);
}
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;
}