Pagini recente » Cod sursa (job #2943706) | Cod sursa (job #500387) | Cod sursa (job #2641026) | Cod sursa (job #2115413) | Cod sursa (job #1966509)
#include <bits/stdc++.h>
#define pii pair <int, int>
#define mp make_pair
#define maxN 100002
FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);
using namespace std;
int N, M;
vector <int> G[maxN];
bitset <maxN> used;
stack <pii> st;
vector <int> aux;
vector < vector<int> >bcc;
int parent[maxN], disc[maxN], low[maxN], t;
void build_BCC(pii p){
pii edge;
do{
edge = st.top();
st.pop();
aux.push_back(edge.first);
aux.push_back(edge.second);
}while(edge != p);
sort(aux.begin(), aux.end());
aux.erase(unique(aux.begin(), aux.end()), aux.end());
bcc.push_back(aux);
aux.clear();
}
void dfs(int node){
low[node] = disc[node] = ++t;
for(int son : G[node])
if(!disc[son]){
parent[son] = node;
st.push(mp(node, son));
dfs(son);
low[node] = min(low[node], low[son]);
if(low[son] >= disc[node]) // find a BCC
build_BCC(mp(node, son));
}
else if(son != parent[node] && disc[son] < low[node]){
low[node] = disc[son]; // just one back edge
st.push(mp(node, son));
}
}
int main(){
scanf("%d %d", &N, &M);
for(int i = 1; i <= M; ++ i){
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
printf("%d\n", (int)bcc.size());
for(auto comp : bcc){
for(auto node : comp)
printf("%d ", node);
printf("\n");
}
return 0;
}