Pagini recente » Cod sursa (job #399264) | Cod sursa (job #2702405) | Cod sursa (job #1786107) | Cod sursa (job #2383202) | Cod sursa (job #2749250)
#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<vector<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]){
vector<int> ctc;
unordered_map<int, bool> viz;
while(true){
auto top = edges_stack.top();
edges_stack.pop();
if(viz[top.first] == false){
ctc.push_back(top.first);
viz[top.first] = true;
}
if(viz[top.second] == false){
ctc.push_back(top.second);
viz[top.second] = true;
}
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);
adj[y].push_back(x);
}
tarjan(n, m);
g << ctcs.size() << '\n';
for(auto ctc : ctcs){
for(auto c : ctc){
g << c << " ";
}
g << '\n';
}
}