Pagini recente » Cod sursa (job #1939687) | Cod sursa (job #1543557) | Clasament oji_go_11_12_2 | Autentificare | Cod sursa (job #2919462)
#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], _dep[MAXN], dd;
bool in[MAXN];
void dfs( int u ) {
stk.push_back(u);
in[u] = true;
dep[u] = _dep[u] = dd++;
for ( auto v : G[u] ) {
if ( _dep[v] == -1 ) {
dfs(v);
dep[u] = min( dep[u], dep[v] );
} else if ( in[v] ) {
dep[u] = min( dep[u], _dep[v] );
}
}
if ( dep[u] == _dep[u] ) {
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);
}
}
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 ) {
dep[i] = _dep[i] = -1;
}
for ( int i = 1; i <= n; ++i ) {
if ( _dep[i] == -1 ) dfs(i);
}
fout << comps.size() << "\n";
for ( auto c : comps ) {
for ( auto x : c ) {
fout << x << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}