Pagini recente » Cod sursa (job #553307) | Cod sursa (job #2191834) | Cod sursa (job #2932607) | Cod sursa (job #363888) | Cod sursa (job #2324689)
#include <cstdio>
#include <stack>
#include <vector>
#define nmax 100001
using namespace std;
FILE *f,*g;
int n,m;
bool viz1[nmax],viz2[nmax];
stack <int> S;
vector <int> V[nmax];
vector <int> Vt[nmax];
vector <int> V2[nmax];
void Citire()
{
int i,x,y;
fscanf(f,"%d%d",&n,&m);
for(i=1; i<=m; i++)
{
fscanf(f,"%d%d",&x,&y);
V[x].push_back(y);
Vt[y].push_back(x);
}
}
void DFS1(int x)
{
int i;
vector <int>::iterator it;
viz1[x]=1;
for(it=V[x].begin(); it!=V[x].end(); it++)
if(!viz1[*it]) DFS1(*it);
S.push(x);
}
void DFS2(int x, int k)
{
int i;
vector <int>::iterator it;
viz2[x]=1;
for(it=Vt[x].begin(); it!=Vt[x].end(); it++)
if(!viz2[*it]) DFS2(*it,k);
V2[k].push_back(x);
}
int main()
{
int c,k=0,i;
vector <int>::iterator it;
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
Citire();
fclose(f);
for(i=1; i<=n; i++)
if(viz1[i]==0) DFS1(i);
while(!S.empty())
{
c=S.top();
S.pop();
if(viz2[c]==0)
{
k++;
DFS2(c,k);
}
}
fprintf(g,"%d",k);
fprintf(g,"\n");
for(i=1; i<=n; i++)
{
for(it=V2[i].begin(); it!=V2[i].end(); ++it)
fprintf(g,"%d ",*it);
fprintf(g,"\n");
}
return 0;
}