Pagini recente » Cod sursa (job #702210) | Cod sursa (job #379542) | Cod sursa (job #2173268) | Cod sursa (job #1362985) | Cod sursa (job #2498243)
#include <cstdio>
#include <vector>
#include <set>
#include <stack>
#define u first
#define v second
using namespace std;
const int NMAX = 100000;
typedef pair <int , int> ii;
vector <int> G[NMAX + 5];
vector <set <int> > comp;
stack <ii> st;
int dfn[NMAX + 5] , low[NMAX + 5] , nrcomp , top , ord , start;
void comp_biconexa(int u , int v)
{
nrcomp ++;
set <int> s;
ii aux;
do
{
aux = st.top();
st.pop();
if(s.find(aux.u) == s.end())
s.insert(aux.u);
if(s.find(aux.v) == s.end())
s.insert(aux.v);
top --;
}
while(aux.u != u && aux.v != v);
comp.push_back(s);
}
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])
st.push(make_pair(u , 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;
st.push(make_pair(-1 , 1));
dfs(1 , -1);
set <int>::iterator it;
printf("%d\n" , nrcomp);
for(i = 0 ; i < comp.size() ; i ++)
{
for(it = comp[i].begin() ; it != comp[i].end() ; it ++)
printf("%d " , (*it));
printf("\n");
}
return 0;
}