Pagini recente » Cod sursa (job #862386) | Cod sursa (job #914027) | Cod sursa (job #1028578) | Cod sursa (job #258715) | Cod sursa (job #2919459)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
const int MAXN = 100005;
vector<int> G[MAXN];
vector<vector<int>> comps;
vector<int> stk;
int dep[MAXN];
bool in[MAXN], viz[MAXN];
int dfs( int u, int d ) {
stk.push_back(u);
viz[u] = in[u] = true;
dep[u] = d;
for ( auto v : G[u] ) {
if ( dep[v] == 0 ) {
dep[u] = min( dep[u], dfs(v, d + 1) );
} else if ( in[v] ) {
dep[u] = min( dep[u], dep[v] );
}
}
if ( dep[u] == d ) {
vector<int> c;
while ( stk.back() != u ) {
c.push_back(stk.back());
in[stk.back()] = false;
stk.pop_back();
}
c.push_back(u);
in[u] = false;
stk.pop_back();
comps.push_back(c);
}
return dep[u];
}
int getNum() {
int n = 0;
char ch;
while ( isspace( ch = fin.get() ) );
do {
n = n * 10 + ch - '0';
} while ( isdigit( ch = fin.get() ) );
return n;
}
int main() {
int n, m, u, v;
n = getNum(), m = getNum();
while ( m-- ) {
u = getNum(), v = getNum();
G[u].push_back(v);
}
for ( int i = 1; i <= n; ++i ) {
if ( !viz[i] ) dfs(i, 1);
}
fout << comps.size() << "\n";
for ( auto c : comps ) {
for ( auto x : c ) {
fout << x << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}