Pagini recente » Cod sursa (job #1062582) | Cod sursa (job #3225708) | Cod sursa (job #2939832) | Cod sursa (job #403175) | Cod sursa (job #3166633)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[NMAX],GT[NMAX],ctc[NMAX];
int viz[NMAX],z[NMAX],n,m,k,nrc;
void dfs(int x);
void dfst(int x);
int main()
{
int i,j,x,y;
fin>>n>>m;
for(i=1; i<=m; i++)
{
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(i=1; i<=n; i++)
if(viz[i]==0)
dfs(i);
for(i=1; i<=n; i++) viz[i]=0;
for(i=1; i<=n; i++)
if(viz[i]==0)
{
nrc++;
dfst(i);
}
fout<<nrc<<'\n';
for(i=1; i<=n; i++)
{
for(j=0; j<ctc[i].size(); j++)
fout<<ctc[i][j]<<' ';
fout<<'\n';
}
return 0;
}
void dfs(int x)
{
int w,j;
viz[x]=1;
for(j=0; j<G[x].size(); j++)
{
w=G[x][j];
if(viz[w]==0)
dfs(w);
}
k++;
z[k]=x;
}
void dfst(int x)
{
int w,j;
viz[x]=1;
ctc[nrc].push_back(x);
for(j=0; j<GT[x].size(); j++)
{
w=GT[x][j];
if(viz[w]==0)
dfst(w);
}
}