Pagini recente » Cod sursa (job #2918157) | Cod sursa (job #636694) | Cod sursa (job #1187014) | Cod sursa (job #1772062) | Cod sursa (job #2082732)
#include <bits/stdc++.h>
#define dim 100002
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
vector < int > v1[dim];
vector < int > v2[dim];
vector < int > v3[dim];
int n,m,i,j,x,y,seen[dim], vec[dim], k;
void read()
{
f >> n >> m;
for(int i = 1; i <= m; i++)
{
f >> x >> y;
v1[x].push_back(y);
v2[y].push_back(x);
}
}
void dfs1(int x)
{
seen[x] = 1;
int l = v2[x].size(), next_x;
for(int i = 0; i < l; i++)
{
next_x = v2[x][i];
if(not seen[next_x])
dfs1(next_x);
}
vec[++k] = x;
}
void dfs2(int x)
{
seen[x] = -1;
int l = v1[x].size(), next_x;
for(int i = 0; i < l; i++)
{
next_x = v1[x][i];
if(seen[next_x] != -1)
dfs2(next_x);
}
v3[k].push_back(x);
}
int main()
{
read();
for(int i = 1; i <= n; i++)
if(not seen[i])
dfs1(i);
k = 0;
for(int i = n; i >= 1; i--)
if(seen[vec[i]] != -1)
{
k++;
dfs2(vec[i]);
}
g << k << '\n';
for(int i = 1; i <= k; i++)
{
int l = v3[i].size();
for(int j = 0; j < l; j++)
g << v3[i][j] << " ";
g << '\n';
}
return 0;
}