Pagini recente » Cod sursa (job #853881) | Cod sursa (job #1058349) | Cod sursa (job #627748) | Cod sursa (job #1904848) | Cod sursa (job #3040836)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
vector <int> edges[NMAX + 1];
vector <vector <int>> comp;
int found_time[NMAX + 1], min_found[NMAX + 1];
bool onStack[NMAX + 1];
stack <int> st;
int t = 0;
void dfs( int node ) {
found_time[node] = min_found[node] = ++t;
onStack[node] = true;
st.push( node );
for ( auto vec : edges[node] ) {
if ( !found_time[vec] ) {
dfs( vec );
min_found[node] = min( min_found[node], min_found[vec] );
} else if ( onStack[vec] ) {
min_found[node] = min( min_found[node], found_time[vec] );
}
}
if ( min_found[node] == found_time[node] ) {
vector <int> componenta;
int aux;
do {
aux = st.top();
componenta.push_back( aux );
onStack[aux] = false;
st.pop();
} while ( aux != node );
comp.push_back( componenta );
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, i, a, b;
fin >> n >> m;
for ( i = 0; i < m; i ++ ) {
fin >> a >> b;
edges[a].push_back( b );
}
for ( int i = 1; i <= n; i ++ ) if ( !found_time[i] ) dfs( i );
fout << comp.size() << '\n';
for ( auto componenta : comp ) {
for ( auto node : componenta ) fout << node << ' ';
fout << '\n';
}
return 0;
}