Pagini recente » Cod sursa (job #1829391) | Cod sursa (job #2687826) | Cod sursa (job #28563) | Cod sursa (job #127354) | Cod sursa (job #1713651)
#include<cstdio>
#include<vector>
#include<stack>
#define MAXN 100010
using namespace std;
vector<int> g[MAXN];
vector<int> component[MAXN];
stack<pair<int,int> > Stack;
int depth[MAXN],low[MAXN],seen[MAXN];
int components=0;
int minimum(int a,int b){
if(a<b)
return a;
return b;
}
void CreateComponent(int node1,int node2){
components++;
int x=Stack.top().first,y=Stack.top().second;
while(Stack.top().first!=node1&&Stack.top().second!=node2){
component[components].push_back(Stack.top().second);
Stack.pop();
}
component[components].push_back(node2);
component[components].push_back(node1);
Stack.pop();
}
void DFS(int node,int father){
int i;
depth[node]=low[node]=depth[father]+1;
seen[node]=1;
for(i=0;i<g[node].size();i++){
if(seen[g[node][i]]==0){
Stack.push(make_pair(node,g[node][i]));
DFS(g[node][i],node);
if(low[g[node][i]]>=depth[node])
CreateComponent(node,g[node][i]);
}
if(g[node][i]!=father)
low[node]=minimum(low[node],low[g[node][i]]);
}
}
int main(){
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n,m,a,b,i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
DFS(1,0);
printf("%d\n",components);
for(i=1;i<=components;i++){
for(j=0;j<component[i].size();j++)
printf("%d ",component[i][j]);
printf("\n");
}
return 0;
}