Pagini recente » Cod sursa (job #958395) | Cod sursa (job #1842112) | Cod sursa (job #700871) | Cod sursa (job #448956) | Cod sursa (job #2217271)
#include <bits/stdc++.h>
#define lim 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> graph[lim];
vector <int> reversed_Graph[lim];
vector <int> answer[lim];
stack <int> road;
int f[lim];
void resetFrequency(int n)
{
for ( int i = 1; i <= n; ++i )
f[i] = 0;
}
void dfs( int node )
{
f[node] = 1;
for ( auto x:graph[node] )
if ( f[x] == 0 )
dfs(x);
road.push(node);
}
void reverseDfs( int node, int solution_Count )
{
f[node] = 1;
for ( auto x:reversed_Graph[node] )
if ( f[x] == 0 )
reverseDfs(x, solution_Count);
answer[solution_Count].push_back(node);
}
int main()
{
int n, m;
fin>>n>>m;
int a, b;
while ( m-- )
{
fin>>a>>b;
graph[a].push_back(b);
reversed_Graph[b].push_back(a);
}
for ( int i = 1; i <= n; ++i )
if ( f[i] == 0 )
dfs(i);
resetFrequency(n);
int solution_Count = 0;
while ( !road.empty() )
{
if ( f[road.top()] == 0 )
reverseDfs(road.top(), ++solution_Count);
road.pop();
}
fout<<solution_Count<<'\n';
for ( int i = 1; i <= n; ++i )
{
for ( auto x:answer[i] )
fout<<x<<" ";
fout<<'\n';
}
}