Pagini recente » Cod sursa (job #508340) | Cod sursa (job #496677) | Cod sursa (job #1959932) | Cod sursa (job #842382) | Cod sursa (job #3040879)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#define MAXN 100005
#define MAXM 200005
#define INFI 1000000
using namespace std;
struct XYZ{
int x,y;
};
vector <int> graf[MAXN];
vector <int> answ[MAXN];
int visi[MAXN];
int adan[MAXN];
int arti[MAXN];
int mini[MAXN];
int t,poz;
void AddEdge(XYZ a){
graf[a.x].push_back(a.y);
graf[a.y].push_back(a.x);
}
void DFS(int node,int d,int fath){
int mi=INFI,c;
visi[node]=1;
adan[node]=d;
mini[node]=d;
mi=d;
c=0;
for(int neigh : graf[node]){
if(visi[neigh]==0){
DFS(neigh,d+1,node);
if(mi>mini[neigh] && neigh!=fath){
mi=mini[neigh];
}
c++;
}
}
if(mi>=d && c>0){
arti[node]=1;
t++;
}
mi=d;
for(int neigh : graf[node]){
if(mi>mini[neigh] && neigh!=fath){
mi=mini[neigh];
}
}
mini[node]=mi;
}
void DFS2(int node,int i){
answ[i].push_back(node);
visi[node]=1;
for(int neigh : graf[node]){
if(visi[neigh]==0){
if(arti[neigh]==1){
if(arti[node]==0){
answ[i].push_back(neigh);
}else{
poz++;
answ[poz].push_back(node);
answ[poz].push_back(neigh);
}
poz++;
DFS2(neigh,poz);
}else{
DFS2(neigh,i);
}
}
}
}
int main(){
int n,m,i,x,y;
FILE *fin,*fout;
fin=fopen("biconex.in","r");
fout=fopen("biconex.out","w");
fscanf(fin,"%d%d",&n,&m);
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&x,&y);
AddEdge({x,y});
}
t=1;
DFS(1,1,-1);
fprintf(fout,"%d\n",t);
for(i=1;i<=n;i++){
visi[i]=0;
}
poz=0;
DFS2(1,0);
for(i=0;i<t;i++){
for(int r:answ[i]){
fprintf(fout,"%d ",r);
}
fprintf(fout,"\n");
}
fclose(fin);
fclose(fout);
return 0;
}