Pagini recente » Rating Barnea Matei (Mathew2003) | Rating Dinca Silviu (Silviu45) | Cod sursa (job #2813459) | Profil n6v26r | Cod sursa (job #1632183)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
int N, M;
vector<int> con[100001];
int crt;
int desc[100001], low[100001];
vector<vector<int> > ww;
stack<int> st;
void dfs(int nod) {
int i;
st.push(nod);
for(i = 0; i < con[nod].size(); i++) {
int u = con[nod][i];
if(!desc[u]) {
low[u] = desc[u] = (++crt);
dfs(u);
if(low[u] < low[nod])
low[nod] = low[u];
} else {
if(low[nod] > low[u]) {
low[nod] = low[u];
}
}
}
if(desc[nod] == low[nod]) {
ww.push_back(vector<int>());
while(true) {
int u = st.top();
st.pop();
ww.back().push_back(u);
if(u == nod)
break;
}
}
}
int main() {
int i, j;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &N, &M);
for(i = 0; i < M; i++) {
int a, b;
scanf("%d %d", &a, &b);
con[a].push_back(b);
}
for(i = 1; i <= N; i++) {
if(!desc[i]) {
desc[i] = low[i] = (++crt);
dfs(i);
}
}
printf("%d\n", ww.size());
for(i = 0; i < ww.size(); i++) {
for(j = 0; j < ww[i].size(); j++) {
printf("%d ", ww[i][j]);
}
printf("\n");
}
return 0;
}