Pagini recente » Cod sursa (job #2326873) | Cod sursa (job #3262690) | Cod sursa (job #2346851) | Cod sursa (job #3166494) | Cod sursa (job #2749247)
#include <fstream>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> adj[100005];
int n, m, timestamp;
vector<set<int>> ctcs;
void dfs(int node, vector<int> &found, vector<int> &low_link, stack<pair<int,int>> &edges_stack){
found[node] = ++timestamp;
low_link[node] = timestamp;
for (int neigh : adj[node]){
if (found[neigh] != 0){
low_link[node] = min(low_link[node], found[neigh]);
}
if (found[neigh] != 0)
continue;
edges_stack.push(make_pair(node, neigh));
dfs(neigh, found, low_link, edges_stack);
low_link[node] = min(low_link[node], low_link[neigh]);
if (low_link[neigh] >= found[node]){
set<int> ctc;
while(true){
auto top = edges_stack.top();
edges_stack.pop();
ctc.insert(top.first);
ctc.insert(top.second);
if (top.first == node && top.second == neigh){
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;
stack<pair<int,int>> edges_stack;
vector<bool> in_stack(n+1, 0);
for (int i = 1 ; i <= n; i ++){
if (found[i] == 0){
dfs(i, found, low_link, edges_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(auto c : ctc){
g << c << " ";
}
g << '\n';
}
}