Pagini recente » Cod sursa (job #3036802) | Cod sursa (job #418416) | Cod sursa (job #527280) | Cod sursa (job #2697359) | Cod sursa (job #2811035)
#include <bits/stdc++.h>
#define NMax 100000
using namespace std;
ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
int n, m;
int u, v;
int nr;
vector<int> adj1[NMax + 1], adj2[NMax + 1];
int comp[NMax + 1];
bool viz1[NMax + 1];
stack<int> st;
vector<int> ans[NMax + 1];
void dfs1 ( int v )
{
viz1[v] = 1;
for ( auto u: adj1[v] )
if ( !viz1[u] )
dfs1(u);
st.push(v);
}
void dfs2 ( int v )
{
comp[v] = nr;
ans[nr].push_back(v);
for ( auto u: adj2[v] )
if ( !comp[u] )
dfs2(u);
}
int main()
{
fin >> n >> m;
for ( int i = 1; i <= m; i++ )
{
fin >> u >> v;
adj1[u].push_back(v);
adj2[v].push_back(u);
}
for ( int i = 1; i <= n; i++ )
if ( !viz1[i] )
dfs1(i);
while ( !st.empty() )
{
int x = st.top(); st.pop();
if ( !comp[x] )
{
nr++;
dfs2(x);
}
}
fout << nr << '\n';
for ( int i = 1; i <= nr; i++ )
{
for ( auto x: ans[i] ) fout << x << " ";
fout << '\n';
}
return 0;
}