Pagini recente » Cod sursa (job #1379117) | Cod sursa (job #682317) | Cod sursa (job #2807952) | Rating Stan Vladut Angel (vlad008) | Cod sursa (job #1514679)
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
FILE *fin, *fout;
int n,m,nrtc,VIZ[100001];
vector < int > G[100001];
vector < int > T[100001];
vector < int > A[100001];
stack < int > stiva;
void DFS1(int nod)
{
vector < int > :: iterator it;
VIZ[nod]=1;
for(it=G[nod].begin(); it!=G[nod].end(); it++)
{
if(VIZ[*it]==0)
{
DFS1(*it);
}
}
stiva.push(nod);
}
void DFS2(int nod)
{
vector < int > :: iterator it;
VIZ[nod]=nrtc;
A[nrtc].push_back(nod);
for(it=T[nod].begin(); it!=T[nod].end(); it++)
{
if(VIZ[*it]==0)
{
DFS2(*it);
}
}
}
int main()
{
fin=fopen("ctc.in","r");
fout=fopen("ctc.out","w");
fscanf(fin,"%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int x,y;
fscanf(fin,"%d%d",&x,&y);
G[x].push_back(y);
T[y].push_back(x);
}
//le bagam toate in stiva cu dfs
for(int i=1; i<=n; i++)
{
if(VIZ[i]==0)
{
DFS1(i);
}
}
//resetam viz
fill(VIZ+1,VIZ+n+1,0);
//parcurgem stiva si facem dfs pe graficul transpus
while(!stiva.empty())
{
if(VIZ[stiva.top()]==0)
{
nrtc++;
DFS2(stiva.top());
}
stiva.pop();
}
vector < int > :: iterator it;
fprintf(fout,"%d\n",nrtc);
for(int i=1;i<=nrtc;i++){
for(it=A[i].begin();it!=A[i].end();it++){
fprintf(fout,"%d ",*it);
}
fprintf(fout,"\n");
}
}