Pagini recente » Cod sursa (job #3209479) | Cod sursa (job #728306) | Cod sursa (job #242715) | Cod sursa (job #2851081) | Cod sursa (job #1363216)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;
int n;
vector<int> vec1[100010];
vector<int> vec2[100010];
vector<int> postfix;
vector<vector<int> > sol;
bitset<100010> viz1;
bitset<100010> viz2;
void dfs1(int x)
{
if(viz1[x])
return;
viz1[x] = 1;
for(int i = 0; i < vec1[x].size(); i++)
dfs1(vec1[x][i]);
postfix.push_back(x);
}
void dfs2(int x, vector<int> & v)
{
if(viz1[x] == 0 || viz2[x])
return;
viz2[x] = 1;
for(int i = 0; i < vec2[x].size(); i++)
dfs2(vec2[x][i], v);
v.push_back(x);
}
void citire()
{
int m, x, y;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
scanf("%d%d", &x, &y);
vec1[x].push_back(y);
vec2[y].push_back(x);
}
}
void solve()
{
for(int i = 1; i <= n; i++)
if(!viz1[i])
dfs1(i);
reverse(postfix.begin(), postfix.end());
for(int i = 0; i < n; i++)
if(!viz2[postfix[i]])
{
vector<int> nou;
dfs2(postfix[i], nou);
sol.push_back(nou);
}
}
void afisare()
{
printf("%d\n", sol.size());
for(int i = 0; i < sol.size(); i++)
{
for(int j = 0; j < sol[i].size(); j++)
printf("%d ", sol[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citire();
solve();
afisare();
return 0;
}