Mai intai trebuie sa te autentifici.
Cod sursa(job #729839)
Utilizator | Data | 30 martie 2012 12:42:56 | |
---|---|---|---|
Problema | Componente biconexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.55 kb |
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100002
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> V[nmax];
vector<int> Sol[nmax];
stack<pair<int,int> > S;
int N,M,K;
int Intoarcere[nmax],Nivel[nmax],T[nmax],Atinge;
inline int _min(int a,int b){if(a<b)return a;return b;}
inline void Adauga(int nod,int tata)
{
int a,b;
for(;a!=nod&&b!=tata;)
{
a = S.top().first;
b = S.top().second;
S.pop();
Sol[K].push_back(a);
}
Sol[K].push_back(tata);
K++;
}
void DFS(int nod)
{
int y,i;
Intoarcere[nod] = Nivel[nod];
for(i=0;i<V[nod].size();i++)
{
y = V[nod][i];
if(!Nivel[y])
{
T[y] = nod;
S.push(make_pair(y,nod));
Nivel[y] = Nivel[nod]+1;
if(y==1)
Atinge++;
DFS(y);
Intoarcere[nod]=_min(Intoarcere[nod],Intoarcere[y]);
if(Intoarcere[y]>=Nivel[nod])//nu pot ajunge mai sus in arbore->nod critic
Adauga(y,nod);
}
else if(y!=T[nod])
Intoarcere[nod]=_min(Intoarcere[nod],Nivel[y]);
}
}
int main()
{
int x,y;
in>>N>>M;
while(M--)
{
in>>x>>y;
V[x].push_back(y),V[y].push_back(x);
}
Nivel[1] = 1;
DFS(1);
out<<K<<'\n';
for(x=0;x<K;x++)
{
for(y=0;y<Sol[x].size();y++)
out<<Sol[x][y]<<' ';
out<<'\n';
}
return 0;
}