Pagini recente » Cod sursa (job #1158774) | Cod sursa (job #2120120) | Cod sursa (job #2454223) | Cod sursa (job #2501850) | Cod sursa (job #2381226)
#include <bits/stdc++.h>
#define nmax 100001
using namespace std;
vector <int> G[nmax];
int d[nmax];
int l[nmax];
bool seen[nmax];
bool articulation[nmax];
vector <int> q;
vector <int> sol[nmax];
int nrsol;
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()!=dest){
sol[nrsol].push_back(q.back());
q.pop_back();
}
sol[nrsol].push_back(q.back());
q.pop_back();
sol[nrsol].push_back(node);
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()
{
FILE *fin, *fout;
fin=fopen("biconex.in","r");
fout=fopen("biconex.out","w");
int n,m,i,j;
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");
}
// fprintf(fout,"\n");
// for(i=1;i<=n;i++){
// if(articulation[i])
// fprintf(fout,"%d ",i);
// }
fclose(fin);
fclose(fout);
return 0;
}