Pagini recente » Cod sursa (job #1705498) | Cod sursa (job #672861) | Cod sursa (job #533408) | Cod sursa (job #2708773) | Cod sursa (job #751804)
Cod sursa(job #751804)
#include<fstream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<algorithm>
#define nmax 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct muchie {int d1, d2;};
int n, *A[nmax], m;
int low[nmax], Niv[nmax], T[nmax], Vf;
bool viz[nmax];
muchie S[200005];
vector <int> v[nmax];
int nr_comp_biconexe;
inline int mini(int a,int b)
{
return a > b ? b : a;
}
void adauga(int nod, int tata)
{
int a, b;
while( a!= nod && b != tata)
{
a = S[Vf].d1;
b = S[Vf].d2;
--Vf;
v[nr_comp_biconexe].push_back(a);
}
v[nr_comp_biconexe].push_back(tata);
nr_comp_biconexe++;
}
void DFS(int nod)
{
int y,i ;
low[nod] = Niv[nod];
for(i = 1; i <= A[nod][0] ; i++)
{
y = A[nod][i];
if(Niv[y] == 0 )
{
T[y] = nod;
S[++Vf].d1 = y;
S[Vf].d2 = T[y];
Niv[y] = Niv[nod] + 1;
DFS(y);
low[nod] = mini(low[y], low[nod] );
if(low[y] >= Niv[nod])// nu pot ajunge mai sus decat tatal nodului y in arbore-> nod critic
adauga(y, nod);
}
else
if(y != T[nod])
low[nod] = mini(low[nod], Niv[y]);
}
}
void read()
{
int x, y;
fin >> n >> m;
for(int i=1; i <= n ;++i)
{
A[i] = (int *) realloc(A[i], sizeof(int));
A[i][0] = 0;
}
for(int i = 1; i <= m ; i++)
{
fin >> x >>y;
A[x][0]++;
A[y][0]++;
A[x] = (int *) realloc(A[x],sizeof(int) * (A[x][0] + 1 ));
A[x][A[x][0]] = y;
A[y] = (int *) realloc(A[y], sizeof(int) * (A[y][0] + 1));
A[y][A[y][0]] = x;
}
}
int main()
{
read();
Niv[1] = 1;
DFS(1);
fout << nr_comp_biconexe <<'\n';
for(int i = 0 ;i < nr_comp_biconexe; ++i)
{
sort(v[i].begin(), v[i].end());
for(int j = 0 ;j < v[i].size(); j++ )
fout << v[i][j] << " " ;
fout <<'\n';
}
fin.close();
return 0;
}