Pagini recente » Cod sursa (job #1292919) | Cod sursa (job #961643) | Cod sursa (job #1475558) | Cod sursa (job #311990) | Cod sursa (job #2925849)
//#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
ifstream fileIn("ctc.in");
ofstream fileOut("ctc.out");
class Graph {
int N;
int M;
vector<vector<int>> list_ad;
vector<vector<int>> ctc;
int count_ctc;
public:
void read();
void ctc_tarjan();
void strong_connected(int node, vector<int>& index, vector<int>& lowlink,
vector<bool>& onstack, stack<int>& stk, int i);
};
void Graph:: read() {
fileIn >> N >> M;
// resize
list_ad.resize(N + 1);
int a, b;
for(int i=0; i<= M-1; i++) {
fileIn >> a >> b;
list_ad[a].push_back(b);
}
}
void Graph::strong_connected(int node, vector<int>& index, vector<int>& lowlink,
vector<bool>& onstack, stack<int>& stk, int i) {
index[node] = lowlink[node] = i++;
stk.push(node);
onstack[node] = true;
for( int neib: list_ad[node]) {
if (index[neib] == -1) {
strong_connected(neib, index, lowlink, onstack, stk, i);
// callback
}
if (onstack[neib]) {
lowlink[node] = min(lowlink[node], lowlink[neib]);
}
}
if (lowlink[node] == index[node]) {
//finished visiting all nodes in the current scc
int k;
count_ctc ++;
ctc.push_back({});
do {
k = stk.top();
stk.pop();
onstack[k] = false;
lowlink[k] = index[node];
ctc[count_ctc].push_back(k);
} while(k != node);
}
}
void Graph::ctc_tarjan() {
count_ctc = 0;
ctc.push_back({});
vector<int> index(N + 1, -1);
vector<int> lowlink(N + 1, -1);
vector<bool> onstack(N + 1, false);
stack<int> stk;
for(int node = 1; node <= N; node++) {
if (index[node] == -1) {
strong_connected(node, index, lowlink, onstack, stk, 0);
}
}
fileOut << count_ctc;
for(auto scc: ctc) {
for( auto comp: scc) {
fileOut << comp << " ";
}
fileOut<< "\n";
}
}
int main() {
Graph my_graph;
my_graph.read();
my_graph.ctc_tarjan();
return 0;
}