Pagini recente » Cod sursa (job #1850021) | Cod sursa (job #343720) | Cod sursa (job #3269928) | Cod sursa (job #2340013) | Cod sursa (job #1230722)
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
#define NMAX 100002
int n, m;
int nr, t[NMAX], numctc, lctc, ct[NMAX], l[NMAX];
bool viz[NMAX];
vector<int>v[NMAX], vinv[NMAX];
void dfs(int nod)
{
for(int i=0; i<v[nod].size(); ++i)
{
int fiu=v[nod][i];
if(!viz[fiu])
{
viz[fiu]=true;
dfs(fiu);
}
}
t[++nr]=nod;
}
void ctc(int nod)
{
ct[++lctc]=nod;
for(int i=0; i<vinv[nod].size(); ++i)
{
int fiu=vinv[nod][i];
if(!viz[fiu])
{
viz[fiu]=true;
ctc(fiu);
}
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int x, y;
scanf("%d%d", &n, &m);
for(int i=1; i<=m; ++i)
{
scanf("%d%d", &x, &y);
v[x].push_back(y);
vinv[y].push_back(x);
}
for(int i=1; i<=n; ++i)
{
if(!viz[i])
{
viz[i]=true;
dfs(i);
}
}
memset(viz, 0, sizeof(viz));
for(int i=n; i>=1; --i)
{
if(!viz[t[i]])
{
l[++numctc]=lctc+1;
viz[t[i]]=true;
ctc(t[i]);
}
}
l[numctc+1]=lctc+1;
printf("%d\n", numctc);
for(int i=1; i<=numctc; ++i)
{
sort(ct+l[i], ct+l[i+1]);
for(int j=l[i]; j<l[i+1]; ++j)
printf("%d ", ct[j]);
printf("\n");
}
return 0;
}