Pagini recente » Cod sursa (job #2569995) | Cod sursa (job #3260305) | Cod sursa (job #1332697) | Cod sursa (job #583219) | Cod sursa (job #3212060)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
const int N = 50000;
vector <int> g[N + 10];
vector <int> gInv[N + 10];
vector <int> st;
vector <int> comp[N + 10];
int viz[N + 10];
int sort_top ( int node ) {
viz[node] = 1;
for ( int i = 0; i < g[node].size(); i++ )
if ( viz[g[node][i]] == 0 )
sort_top (g[node][i]);
st.push_back (node);
return 0;
}
int ctc ( int node, int val ) {
viz[node] = 1;
for ( int i = 0; i < gInv[node].size(); i++ )
if ( viz[gInv[node][i]] == 0 )
ctc (gInv[node][i], val);
comp[val].push_back (node);
return 0;
}
int main () {
int n, m, x, y;
fin >> n >> m;
for ( int i = 0; i < m; i++ ) {
fin >> x >> y;
g[x].push_back (y);
gInv[y].push_back (x);
}
for ( int i = 1; i <= n; i++ )
if ( viz[i] == 0 )
sort_top (i);
reverse ( st.begin() , st.end() );
for ( int i = 1; i <= n; i++ )
viz[i] = 0;
int cnt = 0;
for ( int i = 0; i < n; i++ ) {
if ( viz[st[i]] == 0 ) {
cnt++;
ctc ( st[i], cnt );
}
}
fout << cnt << "\n";
for ( int i = 1; i <= cnt; i++ ) {
for ( int j = 0; j < comp[i].size(); j++ )
fout << comp[i][j] << " ";
fout << "\n";
}
return 0;
}