Pagini recente » Cod sursa (job #2075206) | Cod sursa (job #2117690) | Cod sursa (job #518476) | Cod sursa (job #1692988) | Cod sursa (job #3201978)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> sortaret;
vector <vector <int> > g, inv, componenta;
int grade[100005];
bool viz[100005];
int cnt;
void dfs( int nod ){
viz[nod] = true;
for( auto vec : g[nod] )
if( !viz[vec] )
dfs( vec );
sortaret.push_back(nod);
}
void ctc( int nod ){
viz[nod] = true;
for( auto vec : inv[nod] )
if( !viz[vec] )
ctc( vec );
componenta[cnt].push_back(nod);
}
int main()
{
int n, m;
in >> n >> m;
g.resize(n+1);
inv.resize(n+1);
for( int i = 0; i < m; i++ ){
int a, b;
in >> a >> b;
g[a].push_back(b);
inv[b].push_back(a);
grade[b]++;
}
for( int i = 1; i <= n; i++ )
if( !viz[i] )
dfs(i);
for( int i = 1; i <= n; i++ )
viz[i] = false;
reverse(sortaret.begin(), sortaret.end());
for( auto x : sortaret ){
if( !viz[x] ){
componenta.resize(componenta.size()+1);
ctc(x);
cnt++;
}
}
out << componenta.size() << "\n";
for( auto x : componenta ){
for( auto y : x )
out << y << " ";
out << "\n";
}
return 0;
}