Pagini recente » Cod sursa (job #1439857) | Cod sursa (job #1663777) | Cod sursa (job #3147525) | Cod sursa (job #3038034) | Cod sursa (job #3240295)
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
void dfs(int parent, int node, int& currentTime, stack<int>& st,
vector<int>& tin, vector<int>& low, vector<vector<int>>& bcc, const Graph& G){
if(tin[node] > 0){
return;
}
currentTime += 1;
tin[node] = currentTime;
low[node] = currentTime;
st.push(node);
for(int nextNode: G[node]){
if(nextNode == parent){
// ignore this edge
}else if(tin[nextNode] > 0){
low[node] = min(low[node], tin[nextNode]);
}else{
dfs(node, nextNode, currentTime, st, tin, low, bcc, G);
low[node] = min(low[node], low[nextNode]);
if(tin[node] <= low[nextNode]){
bcc.push_back({node});
while(st.top() != node){
bcc.back().push_back(st.top());
st.pop();
}
}
}
}
}
int main(){
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int N, M;
cin >> N >> M;
Graph G(N + 1);
for(int i = 1; i <= M; ++i){
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
int currentTime = 0;
vector<int> tin(N + 1);
vector<int> low(N + 1);
stack<int> st;
vector<vector<int>> bcc;
for(int node = 1; node <= N; ++node){
if(G[node].empty()){
bcc.push_back({node});
}else{
dfs(-1, node, currentTime, st, tin, low, bcc, G);
}
}
cout << bcc.size() << "\n";
for(vector<int>& nodes: bcc){
for(int node: nodes){
cout << node << " ";
}
cout << "\n";
}
cin.close();
cout.close();
return 0;
}