Pagini recente » Cod sursa (job #3146507) | Cod sursa (job #1821319) | redsnow_3 | Cod sursa (job #235050) | Cod sursa (job #1420868)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
vector<vector<int>> graph, ctc;
vector<int> index, lowlink;
vector<bool> in_stack;
stack<int> st;
int N, M;
int ind = 0;
const char in_file[] = "ctc.in";
const char out_file[] = "ctc.out";
void read_file()
{
ifstream fin(in_file);
int x, y;
fin >> N >> M;
graph.resize(N+1);
index.resize(N+1);
lowlink.resize(N+1);
in_stack.resize(N+1);
index.assign(N+1, -1);
for (int i = 0; i < M; ++i) {
fin >> x >> y;
graph[x].push_back(y);
}
fin.close();
}
inline int minim(const int &a, const int &b) {
return a < b ? a : b;
}
void tarjan(int node)
{
index[node] = ind;
lowlink[node] = ind;
ind++;
st.push(node);
in_stack[node] = true;
for (auto it = graph[node].begin(); it < graph[node].end(); ++it) {
if (index[*it] == -1) {
tarjan(*it);
lowlink[node] = minim(lowlink[node], lowlink[*it]);
}
else if (in_stack[*it]) {
lowlink[node] = minim(lowlink[node], lowlink[*it]);
}
}
if (index[node] == lowlink[node]) {
vector<int> c;
int n;
do {
n = st.top(); st.pop();
in_stack[n] = false;
c.push_back(n);
} while (node != n);
ctc.push_back(c);
}
}
void print_result()
{
ofstream fout(out_file);
fout << ctc.size() << '\n';
for (auto it = ctc.begin(); it < ctc.end(); ++it) {
for (auto jt = it->begin(); jt < it->end(); ++jt)
fout << *jt << ' ';
fout << '\n';
}
fout.close();
}
int main() {
read_file();
for (int i = 1; i < N; ++i)
if (index[i] == -1)
tarjan(i);
print_result();
}