Pagini recente » Cod sursa (job #560047) | Cod sursa (job #1565631) | Cod sursa (job #1458640) | Cod sursa (job #1595598) | Cod sursa (job #2009052)
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;
vector<int> L[MAX_N+1], G[MAX_N+1], v[MAX_N+1];
int f[MAX_N], n, m, k, nrctc;
bool used[MAX_N+1];
void Read()
{
int i, x, y;
FILE *fin = fopen("ctc.in","r");
fscanf(fin,"%d%d",&n,&m);
for(i=1; i<=m; i++)
{
fscanf(fin,"%d%d",&x,&y);
L[x].push_back(y);
G[y].push_back(x);
}
fclose(fin);
}
void DFS(int x)
{
used[x] = true;
for(vector<int>::iterator it = L[x].begin(); it != L[x].end(); it++)
if(!used[(*it)])
DFS(*it);
f[k++] = x;
}
void DFSreverseGraph(int x)
{
used[x] = true;
v[nrctc].push_back(x);
for(vector<int>::iterator it = G[x].begin(); it != G[x].end(); it++)
if(!used[(*it)])
DFSreverseGraph(*it);
}
int main()
{
vector<int>::iterator it;
int i;
FILE *fout = fopen("ctc.out","w");
Read();
for(i=1; i<=n; i++)
if(!used[i])
DFS(i);
for(i=1; i<=n; i++)
used[i] = false;
for(i=k-1; i>=0; i--)
if(!used[f[i]])
{
DFSreverseGraph(f[i]);
nrctc++;
}
fprintf(fout,"%d\n",nrctc);
for(i=0; i<nrctc; i++)
{
for(it = v[i].begin(); it != v[i].end(); it++)
fprintf(fout,"%d ",*it);
fprintf(fout,"\n");
}
fclose(fout);
return 0;
}