Pagini recente » Borderou de evaluare (job #992057) | clasament-arhiva-educationala | Borderou de evaluare (job #1623009) | Borderou de evaluare (job #889110) | Cod sursa (job #1122199)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#define Nmax 100005
using namespace std;
int N,M,nrbic;
vector<int> G[Nmax],sol[Nmax];
int niv[Nmax],low[Nmax];
stack<int> S;
bitset<Nmax> used;
void read()
{
scanf ( "%d%d", &N, &M );
int a,b;
for(int i = 1; i <= M; ++i)
{
scanf ( "%d%d", &a, &b );
G[a].push_back(b);
G[b].push_back(a);
}
}
void biconexa(int nodc,int nodn)
{
++nrbic;
while(S.top() != nodn)
{
sol[nrbic].push_back(S.top());
S.pop();
}
sol[nrbic].push_back(nodn);
sol[nrbic].push_back(nodc);
S.pop();
}
void DFS(int nodc,int daddy)
{
used[nodc] = 1;
niv[nodc] = niv[daddy] + 1;
low[nodc] = niv[nodc];
vector<int>::iterator it;
for(it = G[nodc].begin(); it != G[nodc].end(); ++it)
{
if(*it == daddy)continue;
if(!used[*it]){
S.push(*it);
DFS(*it,nodc);
low[nodc] = min(low[nodc],low[*it]);
if(niv[nodc] <= low[*it])
biconexa(nodc,*it);
continue;
}
low[nodc] = min(low[nodc],niv[*it]);
}
}
void solve()
{
for(int i = 1; i <= N; ++i)
if(!used[i])
{
S.push(i);
DFS(i,0);
S.pop();
}
}
void print()
{
printf("%d\n",nrbic);
for(int i = 1; i <= nrbic; ++i)
{
for(vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
printf("%d ",*it);
printf("\n");
}
}
int main()
{
freopen ( "biconex.in", "r", stdin );
freopen ( "biconex.out", "w", stdout );
read ();
solve ();
print ();
return 0;
}