Pagini recente » Cod sursa (job #3137492) | Cod sursa (job #3264716) | Cod sursa (job #3158881) | Cod sursa (job #2508783) | Cod sursa (job #2656160)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int>> arcs;
vector<int> lowlink, index, components;
vector<bool> onStack;
stack<int> st;
int componentsNo, currentComp;
int min(int x, int y) {
return x<y? x:y;
}
void strongConnect(int x) {
st.push(x);
++currentComp;
lowlink[x] = currentComp;
index[x] = currentComp;
onStack[x] = true;
for(int i=0; i<arcs[x].size(); ++i) {
int nextNode = arcs[x][i];
if (! index[nextNode]) {
strongConnect(nextNode);
lowlink[x] = min(lowlink[x], lowlink[nextNode]);
} else
if (onStack[nextNode])
lowlink[x] = min(lowlink[x], index[nextNode]);
}
if (lowlink[x] == index[x]) {
++componentsNo;
int n;
do {
n = st.top();
onStack[st.top()] = false;
st.pop();
components[n] = componentsNo;
} while (n != x);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m, x, y;
scanf("%d%d", &n, &m);
arcs.resize(n+2);
lowlink.resize(n+2, 0);
index.resize(n+2, 0);
components.resize(n+2, 0);
onStack.resize(n+2, false);
for(int i=0; i<m; ++i) {
scanf("%d%d", &x, &y);
arcs[x].push_back(y);
}
for(int i=1; i<=n; ++i)
if (index[i] == 0)
strongConnect(i);
printf("%d\n", componentsNo);
for(int i=1; i<=componentsNo; ++i) {
for(int j=1; j<=n; ++j)
if (components[j] == i)
printf("%d ", j);
printf("\n");
}
return 0;
}