Pagini recente » Cod sursa (job #1414363) | Cod sursa (job #856193) | Cod sursa (job #976277) | Cod sursa (job #79704) | Cod sursa (job #2498225)
#include <cstdio>
#include <vector>
#include <set>
#define u first
#define v second
using namespace std;
const int NMAX = 100000;
const int MMAX = 200000;
typedef pair <int , int> ii;
vector <int> G[NMAX + 5];
set <int> s[NMAX + 5];
ii st[MMAX];
int dfn[NMAX + 5] , low[NMAX + 5] , nrcomp , top , ord , start;
void comp_biconexa(int u , int v)
{
nrcomp ++;
ii aux;
do
{
aux = st[top];
if(s[nrcomp].find(aux.u) == s[nrcomp].end())
s[nrcomp].insert(aux.u);
if(s[nrcomp].find(aux.v) == s[nrcomp].end())
s[nrcomp].insert(aux.v);
top --;
}
while(aux.u != u && aux.v != v);
}
void dfs(int u , int tu)
{
int v , j;
ord ++;
dfn[u] = low[u] = ord;
for(j = 0 ; j < G[u].size() ; j ++)
{
v = G[u][j];
if(v != tu && dfn[v] < dfn[u])
{
top ++;
st[top].u = u;
st[top].v = v;
}
if(dfn[v] == -1)
{
dfs(v , u);
low[u] = min(low[u] , low[v]);
if(low[v] >= dfn[u])
comp_biconexa(u , v);
}
else if(v != tu)
low[u] = min(low[u] , dfn[v]);
}
}
int main()
{
freopen("biconex.in" , "r" , stdin);
freopen("biconex.out" , "w" , stdout);
int n , m , u , v , i;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= m ; i ++)
{
scanf("%d%d" , &u , &v);
G[u].push_back(v);
G[v].push_back(u);
}
for(i = 1 ; i <= n ; i ++)
dfn[i] = low[i] = -1;
top = 1;
st[1].u = -1;
st[1].v = 1;
dfs(1 , -1);
set <int>::iterator it;
printf("%d\n" , nrcomp);
for(i = 1 ; i <= nrcomp ; i ++)
{
for(it = s[i].begin() ; it != s[i].end() ; it ++)
printf("%d " , (*it));
printf("\n");
}
return 0;
}