Pagini recente » Cod sursa (job #2641676) | Cod sursa (job #2346722) | Cod sursa (job #715702) | Cod sursa (job #1899308) | Cod sursa (job #2901607)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100005
ifstream in("ctc.in");
ofstream out("ctc.out");
unordered_set<int> is_in_stack;
int timestamp = 0;
void dfs(vector<int> graph[NMAX], int node, bool visited[NMAX],
int low_link[], stack<int>& st, int found[], vector<vector<int>>& sccs) {
visited[node] = true;
st.push(node);
is_in_stack.insert(node);
found[node] = ++timestamp;
low_link[node] = found[node];
for (auto& neigh : graph[node]) {
if (!visited[neigh]) {
dfs(graph, neigh, visited, low_link, st, found, sccs);
low_link[node] = min(low_link[node], low_link[neigh]);
} else if (is_in_stack.find(neigh) != is_in_stack.end()) {
low_link[node] = min(low_link[node], low_link[neigh]);
}
}
if (low_link[node] == found[node]) {
vector<int> curr_scc;
while (true) {
if (st.top() == node) {
st.pop();
is_in_stack.erase(node);
break;
}
curr_scc.push_back(st.top());
is_in_stack.erase(st.top());
st.pop();
}
curr_scc.push_back(node);
sccs.push_back(curr_scc);
}
}
vector<vector<int>> tarjan(vector<int> graph[NMAX], int n) {
stack<int> st;
bool visited[NMAX];
int low_link[NMAX];
int found[NMAX];
memset(visited, 0, sizeof(visited));
memset(low_link, 0x3f, sizeof(low_link));
memset(found, 0x3f, sizeof(found));
vector<vector<int>> sccs;
for (int node = 1; node <= n; ++node) {
if (!visited[node]) {
dfs(graph, node, visited, low_link, st, found, sccs);
}
}
return sccs;
}
int main()
{
int n, m;
in >> n >> m;
vector<int> graph[NMAX];
for (int i = 1; i <= m; ++i) {
int x, y;
in >> x >> y;
graph[x].push_back(y);
}
vector<vector<int>> sccs = tarjan(graph, n);
out << sccs.size() << "\n";
for (int i = 0; i < sccs.size(); ++i) {
for (int j = 0; j < sccs[i].size(); ++j) {
out << sccs[i][j] << " ";
}
out << "\n";
}
}