Pagini recente » Cod sursa (job #1339774) | Cod sursa (job #2089810) | Cod sursa (job #82686) | Cod sursa (job #1416423) | Cod sursa (job #703423)
Cod sursa(job #703423)
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
typedef struct nod{ int x; nod *urm;}NODE;
NODE *v[100010];
int n,m,d[100010],minn[100010],k;
stack <pair <int, int> > st;
vector <vector <int> > C;
int minimu(int a, int b)
{
if(a<=b) return a;
return b;
}
void citire()
{
FILE *f=fopen("biconex.in","r");
NODE*q;
int x,y;
fscanf(f,"%d%d",&n,&m);
for(int i=0;i<m;++i)
{
fscanf(f,"%d%d",&x,&y);
q=(NODE*)malloc(sizeof(NODE));
q->x=y;
q->urm = v[x];
v[x] = q;
q=(NODE*)malloc(sizeof(NODE));
q->x=x;
q->urm = v[y];
v[y] = q;
}
fclose(f);
}
void fa(int x,int y)
{
vector <int> tz;
int xx, yy;
do
{
xx = st.top().first;
yy = st.top().second;
st.pop();
tz.push_back(xx);
tz.push_back(yy);
}while(xx!= x || yy != y);
C.push_back(tz);
}
void dfs(int nod,int tata,int dist)
{
d[nod]=minn[nod]=dist;
int nrf=0;
bool critic = false;
NODE *q=v[nod];
while(q)
{
if(q->x != tata)
if(d[q->x]==-1)
{
++nrf;
st.push(make_pair(nod,q->x));
dfs(q->x,nod,dist+1);
minn[nod] = minimu(minn[q->x],minn[nod]);
if(minn[q->x] >= d[nod])
fa(nod,q->x); //critic = true;
}
else
minn[nod] = minimu(minn[nod],d[q->x]);
q=q->urm;
}
}
int main()
{
citire();
for(int i=1;i<=n;++i) d[i]=-1;
dfs(1,0,0);
FILE *f=fopen("biconex.out","w");
fprintf(f,"%d\n",C.size());
for(int i=0;i<C.size(); ++i)
{
sort(C[i].begin(),C[i].end());
int aux=0,j=0;
do
{
fprintf(f,"%d ",C[i][j]);
for(; C[i][j] == C[i][aux] &&j<=C[i].size() ;++j);
aux = j;
}while(j<C[i].size());
fprintf(f,"\n");
}
fclose(f);
return 0;
}