Nu aveti permisiuni pentru a descarca fisierul grader_test4.in
Cod sursa(job #3226886)
| Utilizator | Data | 23 aprilie 2024 10:58:13 | |
|---|---|---|---|
| Problema | Componente biconexe | Scor | 10 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.74 kb |
#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;
}
