Pagini recente » Cod sursa (job #2741530) | Cod sursa (job #1543077) | Cod sursa (job #2687443) | Cod sursa (job #1874796) | Cod sursa (job #2758884)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> adj[100005];
int n, m, timestamp;
vector<vector<int>> ctcs;
void dfs(int node, vector<int> &found, vector<int> &low_link, stack<int> &nodes_stack, vector<bool> &in_stack){
found[node] = ++timestamp;
low_link[node] = timestamp;
nodes_stack.push(node);
in_stack[node] = true;
for (int neigh : adj[node]){
if (found[neigh] != 0 && in_stack[neigh]){
low_link[node] = min(low_link[node], low_link[neigh]);
}
if (found[neigh] != 0)
continue;
dfs(neigh, found, low_link, nodes_stack, in_stack);
low_link[node] = min(low_link[node], low_link[neigh]);
}
if(low_link[node] == found[node])
{
vector<int> ctc;
while(true){
int top = nodes_stack.top();
nodes_stack.pop();
in_stack[top] = false;
ctc.push_back(top);
if (top == node){
break;
}
}
ctcs.push_back(ctc);
}
}
void tarjan(int n, int m){
vector<int> low_link (n + 1, 0);
vector<int> found(n+1, 0);
stack<int> nodes_stack;
vector<bool> in_stack(n+1, 0);
for (int i = 1 ; i <= n; i ++){
if (found[i] == 0){
dfs(i, found, low_link, nodes_stack, in_stack);
}
}
}
int main(){
f >> n >> m;
for (int i = 0 ; i < m; i ++){
int x, y;
f >> x >> y;
adj[x].push_back(y);
}
tarjan(n, m);
g << ctcs.size() << '\n';
for(auto ctc : ctcs){
for(int c : ctc){
g << c << " ";
}
g << '\n';
}
}