Pagini recente » Cod sursa (job #2622260) | Cod sursa (job #462903) | Cod sursa (job #541183) | Istoria paginii runda/cnrv_x1 | Cod sursa (job #1431200)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <stdio.h>
#define MAX 100000
using namespace std;
vector <int> adj[MAX], idx, lowlink, in_stack;
stack <int> st;
int t, component;
vector <vector<int> > components;
int min(int a, int b) {
return (a > b)? b : a;
}
void tarjan(int n) {
idx[n] = lowlink[n] = t;
t++;
st.push(n); in_stack[n] = 1;
for (vector<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it)
if (idx[*it] == -1) {
tarjan(*it);
lowlink[n] = min(lowlink[n], lowlink[*it]);
}
else if (in_stack[*it]) {
lowlink[n] = min(lowlink[n], idx[*it]);
}
if (idx[n] == lowlink[n]) {
int node;
do {
node = st.top();
components[component].push_back(node);
st.pop();
} while (node != n);
component++;
}
}
int main() {
freopen ("ctc.in", "rt", stdin);
freopen ("ctc.out", "wt", stdout);
int n, m;
cin >> n >> m;
int n1, n2;
idx.resize(n+1);
idx.assign(n+1, -1);
lowlink.resize(n+1);
lowlink.assign(n+1, -1);
in_stack.resize(n+1);
in_stack.assign(n+1, 0);
components.resize(n);
for (int i = 0; i < m; ++i) {
cin >> n1 >> n2;
adj[n1].push_back(n2);
}
for (int i = 1; i <= n; ++i)
if (idx[i] == -1)
tarjan(i);
cout << component << "\n";
for (unsigned int i = 0; i < components.size(); ++i) {
for (unsigned int j = 0; j < components[i].size(); ++j)
cout << components[i][j] << " ";
cout << "\n";
}
}