Pagini recente » Cod sursa (job #2484894) | Cod sursa (job #2794809) | Cod sursa (job #1523501) | Cod sursa (job #2330752) | Cod sursa (job #1685360)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>
struct Node {
int index, lowlink;
std::vector<int> list;
Node()
:index(-1), lowlink(-1)
{}
};
std::ifstream fin("grader_test1.in");
std::ofstream fout("ctc.out");
std::stack<int> st;
int level = 0;
std::vector<std::vector<int> >comp;
void dfs(int node, std::vector<Node> &g, bool *on_stack) {
on_stack[node] = true;
g[node].index = level;
g[node].lowlink = level;
level++;
st.push(node);
for (size_t i = 0; i < g[node].list.size(); i++) {
if (g[g[node].list[i]].index == -1) {
dfs(g[node].list[i], g, on_stack);
g[node].lowlink = std::min(g[node].lowlink, g[g[node].list[i]].lowlink);
} else if (on_stack[g[node].list[i]]) {
g[node].lowlink = std::min(g[node].lowlink, g[g[node].list[i]].lowlink);
}
}
if (g[node].lowlink == g[node].index) {
std::vector<int> v;
int top;
do {
top = st.top();
st.pop();
on_stack[top] = false;
v.push_back(top);
}while (top != node);
comp.push_back(v);
}
}
void solve(std::vector<Node> &g, int N) {
bool on_stack[N + 1];
memset(on_stack, false, sizeof(on_stack));
for (int i = 1; i <= N; i++) {
if (g[i].index == -1)
dfs(i, g, on_stack);
}
fout << comp.size() << '\n';
for (size_t i = 0; i < comp.size(); i++) {
for (size_t j = 0; j < comp[i].size(); j++) {
fout << comp[i][j] << " ";
}
fout << '\n';
}
}
int main() {
int N, M;
fin >> N >> M;
std::vector<Node> graph(N + 1);
for (int i = 0; i < M; i++) {
int x, y;
fin >> x >> y;
graph[x].list.push_back(y);
}
bool viz[N + 1];
memset(viz, false, sizeof(viz));
solve(graph, N);
return 0;
}