Pagini recente » Cod sursa (job #3252996) | Cod sursa (job #699644) | Cod sursa (job #998877) | Cod sursa (job #2307501) | Cod sursa (job #1833891)
#include <cstdio>
#include <stack>
#include <vector>
const int nmax=100001;
using namespace std;
FILE *f,*g;
int ct,n,m;
vector <int> G[nmax],Gt[nmax];
vector <int> Ctc[nmax];
stack <int> S;
bool viz[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);
G[x].push_back(y);
Gt[y].push_back(x);
}
fclose(f);
}
void DFSG(int x)
{
vector <int>::iterator it;
viz[x]=1;
for(it=G[x].begin();it!=G[x].end();++it)
if(viz[*it]==0) DFSG(*it);
S.push(x);
}
void DFSGT(int x)
{ int i;
vector <int>::iterator it;
viz[x]=1;
for(it=Gt[x].begin();it!=Gt[x].end();++it)
if(viz[*it]==0) DFSGT(*it);
Ctc[ct].push_back(x);
}
int main()
{
g=fopen("ctc.out","w");
f=fopen("ctc.in","r");
Citire();
int i,x;
for(i=1;i<=n;i++)
if(viz[i]==0)
DFSG(i);
for(i=1;i<=n;i++)
viz[i]=0;
while(!S.empty())
{ x=S.top();
S.pop();
if(viz[x]==0)
{ ct++;
DFSGT(x);
}
}
fprintf(g,"%d\n",ct);
vector <int>::iterator it;
for(i=1;i<=ct;i++)
{for(it=Ctc[i].begin();it!=Ctc[i].end();++it)
fprintf(g,"%d ",*it);
fprintf(g,"\n");
}
return 0;
}