Pagini recente » Cod sursa (job #355717) | Cod sursa (job #2287627) | Cod sursa (job #2975428) | Cod sursa (job #2588861) | Cod sursa (job #2076023)
#include<cstdio>
#include<vector>
#include<stack>
#define MAX_N 100000
using namespace std;
vector<int>G[MAX_N+1], Gt[MAX_N+1], ctc[MAX_N+1];
stack<int>st;
bool used[MAX_N+1];
int n, m, nrctc;
void DFS(int node) {
used[node] = true;
vector<int>::iterator it;
for(it = G[node].begin(); it != G[node].end(); it++)
if(!used[*it])
DFS(*it);
st.push(node);
}
void DFSmaster(int n) {
for(int i = 1; i <= n; i++)
if(!used[i])
DFS(i);
}
void DFSreverseGraph(int node) {
used[node] = true;
ctc[nrctc].push_back(node);
vector<int>::iterator it;
for(it = Gt[node].begin(); it != Gt[node].end(); it++)
if(!used[*it])
DFSreverseGraph(*it);
}
void Kosaraju() {
for(int i = 1; i <= n; i++)
used[i] = false;
while(!st.empty()) {
int node = st.top();
st.pop();
if(!used[node]) {
DFSreverseGraph(node);
nrctc++;
}
}
}
int main() {
int x, y;
vector<int>::iterator it;
FILE *fin, *fout;
fin = fopen("ctc.in","r");
fout = fopen("ctc.out","w");
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);
}
DFSmaster(n);
Kosaraju();
fprintf(fout,"%d\n",nrctc);
for(int i = 0; i < nrctc; i++) {
for(it = ctc[i].begin(); it != ctc[i].end(); it++)
fprintf(fout,"%d ",*it);
fprintf(fout,"\n");
}
fclose(fin);
fclose(fout);
return 0;
}