Pagini recente » Cod sursa (job #2839183) | Cod sursa (job #2644375) | Cod sursa (job #2324446) | Cod sursa (job #1614515) | Cod sursa (job #1896804)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream f("biconex.in");
FILE *g;
int d[100000],low[100000];
int pred[100000], art[100000];
struct muchie
{
int x;
int y;
};
stack <struct muchie> stiva;
void citire_date_despre_graf(int &n,int &m, vector <int> *&l)
{
f>>n>>m;
l=new vector <int> [n+1];
for(int i=1;i<=m;i++)
{
int x,y;
f>>x>>y;
l[x].push_back(y);
l[y].push_back(x);
}
}
int timp=0;
void dfs(int nod, vector <int> *l)
{
timp++;
d[nod]=low[nod]=timp;
int nrc=0;
for(int i=0;i<l[nod].size();i++)
{
if(d[l[nod][i]]==0)
{
nrc++;
pred[l[nod][i]]=nod;
dfs(l[nod][i],l);
if(low[l[nod][i]]>=d[nod]&&nod!=1)
{
art[nod]=1;
}
low[nod]=min(low[nod],low[l[nod][i]]);
struct muchie s;
s.x=nod;
s.y=l[nod][i];
stiva.push(s);
}
else
if(l[nod].size()==1) art[nod]=1;
else
if(pred[nod]!=l[nod][i])
low[nod]=min(low[nod],d[l[nod][i]]);
}
}
int main()
{
g=fopen("biconex.out","w");
fprintf(g," \n");
vector <int> *l;
int n,m;
citire_date_despre_graf(n,m,l);
dfs(1,l);
if(l[1].size()>=2) art[1]=1;
int nrc=0;
int okx=0;
while(!stiva.empty())
{
muchie a=stiva.top();
//fprintf(g,"%d %d\n",a.x,a.y);
if(okx==0)
{
fprintf(g,"%d ",a.x);
okx=1;
}
fprintf(g,"%d ",a.y);
if(art[a.y]==1)
{
fprintf(g,"\n");
okx=0;
nrc++;
}
stiva.pop();
}
fseek(g,0,SEEK_SET);
fprintf(g,"%d",nrc+1);
return 0;
}