Pagini recente » Cod sursa (job #1450882) | Cod sursa (job #594256) | Cod sursa (job #3235631) | Cod sursa (job #1303636) | Cod sursa (job #3123273)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 200000
using namespace std;
vector<vector<int> > ctc;
vector<int> ctc_aux;
void tarjan(int node, vector<int> adj[NMAX], vector<int> &nodeIndex, vector<int> &lowlink,
vector<int> &onStack, stack<int> &st, int &index) {
nodeIndex[node] = lowlink[node] = ++index;
st.push(node);
onStack[node] = true;
int size = adj[node].size();
for (int i = 0; i < size; i++) {
int v = adj[node][i];
if (nodeIndex[v] == -1) {
tarjan(v, adj, nodeIndex, lowlink, onStack, st, index);
lowlink[node] = min(lowlink[node], lowlink[v]);
} else if (onStack[v] == true) {
lowlink[node] = min(lowlink[node], nodeIndex[v]);
}
}
int w = 0;
if (lowlink[node] == nodeIndex[node]) {
ctc_aux.clear();
do {
w = st.top();
ctc_aux.push_back(w);
st.pop();
onStack[w] = false;
} while (w != node);
ctc.push_back(ctc_aux);
}
}
void find_ctc(int n, vector<int> adj[NMAX]) {
vector<int> nodeIndex(n + 1, -1);
vector<int> lowlink(n + 1, -1);
vector<int> onStack(n + 1, false);
stack<int> st;
int index = 0;
for (int i = 1; i <= n; i++) {
if (nodeIndex[i] == -1) {
tarjan(i, adj, nodeIndex, lowlink, onStack, st, index);
}
}
}
void print_ctc() {
ofstream fout("ctc.out");
fout << ctc.size() << "\n";
for (int i = ctc.size() - 1; i >= 0; i--) {
for (int j = ctc[i].size() - 1; j >= 0; j--) {
fout << ctc[i][j] << " ";
}
fout << "\n";
}
}
int main() {
ifstream fin("ctc.in");
int n, m;
fin >> n >> m;
vector<int> adj[n + 1];
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
adj[x].push_back(y);
}
find_ctc(n, adj);
print_ctc();
return 0;
}