Pagini recente » Cod sursa (job #876014) | Cod sursa (job #2780173) | Cod sursa (job #475769) | Cod sursa (job #2894991) | Cod sursa (job #2709659)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
stack <pair <int, int>> st;
vector <vector <int>> bcc;
vector <int> gr[100001];
int tin[100001], low[10001];
int N, M;
void Read(){
f >> N >> M;
while(M--){
int x, y;
f >> x >> y;
gr[x].emplace_back(y);
gr[y].emplace_back(x);
}
}
void find_bcc(int x, int y){
vector <int> con;
int tx, ty;
do{
tx = st.top().first, ty = st.top().second;
st.pop();
con.emplace_back(tx), con.emplace_back(ty);
}while(tx != x || ty != y);
bcc.emplace_back(con);
}
void dfs(int v = 1, int p = 0){
tin[v] = low[v] = tin[p] + 1;
for(int to : gr[v]){
if(to == p) continue;
if(!tin[to]){
st.push({v, to});
dfs(to, v);
low[v] = min(low[v], low[to]);
if(low[to] >= tin[v])
find_bcc(v, to);
}
else low[v] = min(low[v], tin[to]);
}
}
void Print_bcc(){
g << bcc.size() << "\n";
for(int i = 0;i < (int)bcc.size();i++){
sort(bcc[i].begin(), bcc[i].end());
bcc[i].erase(unique(bcc[i].begin(), bcc[i].end()), bcc[i].end());
for(int x : bcc[i])
g << x << " ";
g << "\n";
}
}
int main(){
Read();
dfs();
Print_bcc();
}