Pagini recente » Cod sursa (job #507412) | Cod sursa (job #2189060) | Cod sursa (job #2460060) | Rating Vultur (Oroles) | Cod sursa (job #1833112)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>
#include <stack>
#define N 100005
#define M 200005
using namespace std;
int n, m, nr_articulatii;
vector <int> G[N];
int sus[N], adancime[N];
bitset <N> viz;
stack <int> s;
vector < vector <int> > sol;
void creare_componenta(int nod)
{
vector <int> tmp;
tmp.push_back(s.top());
do
{
s.pop();
tmp.push_back(s.top());
}
while(s.top() != nod);
sol.push_back(tmp);
}
void dfs(int x, int tata)
{
s.push(x);
adancime[x] = adancime[tata] + 1;
sus[x] = adancime[x];
vector <int> :: iterator it;
for(it = G[x].begin() ; it != G[x].end() ; ++it)
{
if(*it == tata)
{
continue;
}
if(!viz[*it])
{
viz[*it] = true;
dfs(*it,x);
sus[x] = min(sus[x],sus[*it]);
if(adancime[x] <= sus[*it])
{
nr_articulatii++;
creare_componenta(x);
}
}
else
{
sus[x] = min(sus[x],adancime[*it]);
}
}
}
void afisare()
{
for(int i = 0 ; i < sol.size() ; ++i)
{
for(int j = 0 ; j < sol[i].size() ; ++j)
{
printf("%d ",sol[i][j]);
}
printf("\n");
}
}
void citire()
{
scanf("%d %d\n",&n,&m);
int x, y;
for(int i = 0 ; i < m ; ++i)
{
scanf("%d %d\n",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
adancime[0] = -1;
for(int i = 1 ; i <= n ; ++i)
{
if(!viz[i])
{
viz[i] = true;
dfs(i,0);
}
}
printf("%d\n",nr_articulatii);
afisare();
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
return 0;
}