Pagini recente » Cod sursa (job #246165) | Cod sursa (job #2534216) | Cod sursa (job #2824500) | Cod sursa (job #1783109) | Cod sursa (job #3226886)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define MAXN 100005
using namespace std;
struct XYZ{
int x,y;
};
vector <int> graf[MAXN];
int adan[MAXN];
int jump[MAXN];
int fath[MAXN];
vector <int> vf[MAXN];
XYZ ans[MAXN];
int k;
int GetFath(int node){
if(fath[node]==node){
return node;
}
fath[node]=GetFath(fath[node]);
return fath[node];
}
void Conect(int a,int b){
int fa,fb;
fa=GetFath(a);
fb=GetFath(b);
fath[fa]=fb;
}
void DFS(int node,int jos,int fath){
int sarit;
jump[node]=jos;
adan[node]=jos;
sarit=jos;
for(int neigh : graf[node]){
if(neigh!=fath){
if(adan[neigh]==0){
DFS(neigh,jos+1,node);
}
sarit=min(sarit,jump[neigh]);
if(jump[neigh]<=adan[node]){
Conect(neigh,node);
}else{
if(node<neigh){
ans[k]={node,neigh};
k++;
}
}
}
}
jump[node]=sarit;
}
int main(){
int n,m,i,x,y,c;
FILE *fin,*fout;
fin=fopen("biconex.in","r");
fout=fopen("biconex.out","w");
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=n;i++){
fath[i]=i;
}
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&x,&y);
graf[x].push_back(y);
graf[y].push_back(x);
}
DFS(1,1,-1);
for(i=1;i<=n;i++){
vf[GetFath(i)].push_back(i);
}
c=0;
for(i=1;i<=n;i++){
if(vf[i].size()>1){
c++;
}
}
fprintf(fout,"%d\n",c+k);
for(i=1;i<=n;i++){
if(vf[i].size()>1){
for(int node : vf[i]){
fprintf(fout,"%d ",node);
}
fprintf(fout,"\n");
}
}
for(i=0;i<k;i++){
fprintf(fout,"%d %d\n",ans[i].x,ans[i].y);
}
fclose(fin);
fclose(fout);
return 0;
}