Pagini recente » Cod sursa (job #1503602) | Cod sursa (job #1128767) | Cod sursa (job #1947237) | Istoria paginii runda/concursdeinfo/clasament | Cod sursa (job #1022421)
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
using namespace std;
const int MAX_N = 100000 + 2;
const int MAX_M = 200000 + 2;
const int UNDEFINED = 0;
vector<int> nodes[MAX_N];
vector<vector<int> > sccs; // strongly connected components
int index[MAX_N], lowlink[MAX_N], current_index = 1;
stack<int> s;
set<int> stack_nodes;
inline void push(int node) {
s.push(node);
stack_nodes.insert(node);
}
inline void pop() {
int node = s.top();
s.pop();
stack_nodes.erase(stack_nodes.find(node));
}
void connect(int node) {
index[node] = current_index;
lowlink[node] = current_index;
current_index++;
push(node);
for (int i = 0; i < (int)nodes[node].size(); i++) {
int neighbour = nodes[node][i];
if (index[neighbour] == UNDEFINED) {
connect(neighbour);
lowlink[node] = min(lowlink[node], lowlink[neighbour]);
} else if (stack_nodes.find(neighbour) != stack_nodes.end()) {
lowlink[node] = min(lowlink[node], index[neighbour]);
}
}
vector<int> scc;
if (lowlink[node] == index[node]) {
int i;
do {
i = s.top();
scc.push_back(i);
pop();
} while (node != i);
sccs.push_back(scc);
}
}
int main(int argc, char *argv[])
{
int n, m, from, to;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d", &from, &to);
nodes[from].push_back(to);
}
for (int i = 1; i <= n; i++) {
if (index[i] == UNDEFINED)
connect(i);
}
printf("%d\n", (int)sccs.size());
for (int i = 0; i < (int)sccs.size(); i++) {
for (int j = 0; j < (int)sccs[i].size(); j++)
printf("%d ", sccs[i][j]);
printf("\n");
}
return 0;
}