Pagini recente » Cod sursa (job #2810336) | Cod sursa (job #2188671) | Cod sursa (job #1369754) | Cod sursa (job #1369142) | Cod sursa (job #2502849)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int DIM = 1e5 + 5;
int K, N, M, low[DIM], niv[DIM], f[DIM], cod;
vector<int> edge[DIM];
vector<int> ctc[DIM];
stack<int> st;
void dfs( int nod ){
niv[nod] = low[nod] = ++cod;
f[nod] = 1;
st.push( nod );
for( int i = 0; i < edge[nod].size(); i++ ){
int vec = edge[nod][i];
if( niv[vec] == 0 ){
dfs( vec );
low[nod] = min( low[nod], low[vec] );
}else{
if( f[vec] == 1 )
low[nod] = min( low[nod], low[vec] );
}
}
if( low[nod] == niv[nod] ){
K++;
while( st.top() != nod ){
ctc[K].push_back( st.top() );
f[ st.top() ] = 0;
st.pop();
}
st.pop();
f[nod] = 0;
ctc[K].push_back( nod );
}
return;
}
int main(){
fin >> N >> M;
for( int i = 1; i <= M; i++ ){
int x, y; fin >> x >> y;
edge[x].push_back( y );
}
cod = 0;
for( int i = 1; i <= N; i++ ){
if( niv[i] == 0 )
dfs( i );
}
fout << K << "\n";
for( int i = 1; i <= K; i++, fout << "\n" )
for( int j = 0; j < ctc[i].size(); j++, fout << " " )
fout << ctc[i][j];
return 0;
}