Pagini recente » Cod sursa (job #1559702) | Cod sursa (job #1314135) | Cod sursa (job #1519489) | Cod sursa (job #826177) | Cod sursa (job #2380570)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define nmax 100001
using namespace std;
vector <int> G[nmax];
//int coada[nmax][2];
//int low[nmax];
//int vizit[nmax];
//int depth[nmax];
//int k=0;
//int count=0;
//vector <int> p[nmax];
int d[nmax];
int l[nmax];
bool seen[nmax];
bool articulation[nmax];
vector <int> q;
vector <int> sol[nmax];
int nrsol;
FILE *fin, *fout;
//void bi(int node, int father, int d){
// low[node]=depth[node]=d;
// vizit[node]=1;
// for(int i=0;i<v[node].size();i++){
// int vecin=v[node][i];
// if(!vizit[vecin] && vecin!=father){
// coada[k][0]=node;
// coada[k][1]=vecin;
// k++;
// bi(vecin,node,d+1);
// low[node]=min(low[node],low[vecin]);
// if(depth[node]<=low[vecin]){
// k--;
// p[count].push_back(coada[k][1]);
// while(coada[k][0]!=node){
// p[count].push_back(coada[k][0]);
// k--;
// }
// p[count].push_back(coada[k][0]);
// count++;
// }
// }else if(vecin!=father){
// low[node]=min(low[node],depth[vecin]);
// }
// }
//}
void get_articulation(int node, int depth, int father){
q.push_back(node);
seen[node]=true;
d[node]=depth;
l[node]=depth;
bool is_art=false;
int child=0;
for(int i=0;i<G[node].size();i++){
int dest=G[node][i];
if(!seen[dest]){
get_articulation(dest, depth+1, node);
child++;
if(l[dest]>=d[node]){
is_art=true;
while(q.back()!=node){
sol[nrsol].push_back(q.back());
q.pop_back();
}
sol[nrsol].push_back(q.back());
nrsol++;
}
l[node]=min(l[node], l[dest]);
}else{
if(dest!=father){
l[node]=min(l[node],l[dest]);
}
}
}
if( (is_art && father!=0) || (father==0 && child>1)){
articulation[node]=true;
}
}
int main()
{
int n,m,i,j;
fin=fopen("biconex.in","r");
fout=fopen("biconex.out","w");
fscanf(fin,"%d%d",&n,&m);
for(m;m>0;m--){
fscanf(fin,"%d%d",&i,&j);
G[i].push_back(j);
G[j].push_back(i);
}
get_articulation(1,1,0);
fprintf(fout,"%d\n",nrsol);
for(i=0;i<nrsol;i++){
for(j=0;j<sol[i].size();j++){
fprintf(fout,"%d ",sol[i][j]);
}
fprintf(fout,"\n");
}
fclose(fin);
fclose(fout);
return 0;
}