Pagini recente » Cod sursa (job #3240814) | Cod sursa (job #1748483) | Cod sursa (job #622852) | Cod sursa (job #3208378) | Cod sursa (job #2930565)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, lastIndex, stronglyConnectedComponents;
vector <vector<int>>v, ctc;
vector <int> index, lowlink;
vector <bool> visited, inStack;
stack <int> stk;
void init() {
v = vector<vector<int>> (n + 1);
index = vector <int> (n + 1);
lowlink = vector <int> (n + 1);
visited = vector <bool> (n + 1);
inStack = vector <bool> (n + 1);
ctc.push_back({});
}
void read() {
fin >> n >> m;
init();
int x, y;
for(int i = 1; i <= m; i ++) {
fin >> x >> y;
v[x].push_back(y);
}
}
void tarjan(int node) {
stk.push(node);
visited[node] = true;
inStack[node] = true;
index[node] = lowlink[node] = ++lastIndex;
for(const auto& neighbor : v[node]) {
if(!visited[neighbor]) { ///tree edge
tarjan(neighbor);
lowlink[node] = min(lowlink[node], lowlink[neighbor]);
}
else if(inStack[neighbor]) { ///back edge
lowlink[node] = min(lowlink[node], index[neighbor]);
}
}
if(lowlink[node] == index[node]) {
++stronglyConnectedComponents;
ctc.push_back({});
int stackNode;
do {
stackNode = stk.top();
ctc[stronglyConnectedComponents].push_back(stackNode);
stk.pop();
inStack[stackNode] = false;
}while(stackNode != node);
}
}
void solve() {
for(int i = 1; i <= n; i ++)
if(!visited[i])
tarjan(i);
fout << stronglyConnectedComponents << '\n';
for(int i = 1; i <= stronglyConnectedComponents; i ++, fout << '\n')
for(const auto& node : ctc[i])
fout << node << ' ';
}
int main() {
read();
solve();
}