Pagini recente » Cod sursa (job #2139310) | Cod sursa (job #82122) | Cod sursa (job #342538) | Cod sursa (job #3171482) | Cod sursa (job #2399138)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100005
struct muchie
{
int x, y;
}S[NMAX];
int T[NMAX], niv[NMAX], low[NMAX], N, nivel, sol, n;
vector<int>G[NMAX], B[NMAX];
void citire(), biconex(), DFS(int), componenta(int, int), afisare();
int main()
{
citire();
biconex();
afisare();
return 0;
}
void citire()
{
ifstream fin("biconex.in");
int m, i, x, y;
fin>>n>>m;
for(int i=1; i<=m; i++)
{
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
fin.close();
}
void componenta(int x, int y)
{
int i, j;
sol++;
do
{
i=S[N].x, j=S[N].y, N--;
B[sol].push_back(j);
}while(i != x && j != y);
}
void DFS(int nod)
{
int fiu;
vector<int>::iterator it, it2;
nivel++;
niv[nod] = low[nod] = nivel;
for(it = G[nod].begin(), it2 = G[nod].end(); it != it2; it++)
{
fiu = *it;
if(*it != T[nod])
{
if(!niv[fiu])
{
N++, S[n].x = nod, S[N].y = fiu;
T[fiu] = nod;
DFS(fiu);
if(low[fiu] >= niv[nod])
componenta(nod, fiu);
low[nod] = min(low[nod], low[fiu]);
}
else
low[nod] = min(low[nod], niv[fiu]);
}
}
}
void biconex()
{
for(int i=1; i<=n; i++)
if(!niv[i])
DFS(i);
}
void afisare()
{
ofstream fout("biconex.out");
vector<int>::iterator it, it2;
fout<<sol<<'\n';
for(int i=1; i<=sol; i++)
{
for(it=B[i].begin(), it2=B[i].end(); it!=it2; it++)
fout<<*it<<" ";
fout<<'\n';
}
}