Pagini recente » Cod sursa (job #2112718) | Cod sursa (job #898053) | Cod sursa (job #571539) | Cod sursa (job #314850) | Cod sursa (job #3184889)
#include <bits/stdc++.h>
#define NN 100005
#define MM 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m, a, b, nrc, vis[NN];
vector <int> g[NN], gt[NN];
int z[NN], nz;
void dfs(int x)
{
int y;
vis[x] = 1;
for(int i = 0 ; i < g[x].size() ; i++)
{
y = g[x][i];
if(vis[y] == 0)
{
dfs(y);
}
}
nz++;
z[nz] = x;
}
void dfst(int x)
{
int y;
vis[x] = nrc;
for(int i = 0 ; i < gt[x].size() ; i++)
{
y = gt[x][i];
if(vis[y] == 0)
{
dfst(y);
}
}
}
int main()
{
fin >> n >> m;
for(int i = 1 ; i <= m ; i++)
{
fin >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
}
for(int i = 1 ; i <= n ; i++)
{
if(vis[i] == 0)
{
dfs(i);
}
}
for(int i = 1 ; i <= n ; i++)
vis[i] = 0;
for(int i = nz ; i > 0 ; i--)
{
if(vis[z[i]] == 0)
{
nrc++;
dfst(z[i]);
}
}
fout << nrc << '\n';
for(int i = 1 ; i <= nrc ; i++)
{
for(int j = 1 ; j <= n ; j++)
{
if(vis[j] == i)
fout << j << ' ';
}
fout << '\n';
}
return 0;
}