Pagini recente » Cod sursa (job #3339672) | Cod sursa (job #715942) | Cod sursa (job #2072161) | Cod sursa (job #1447465) | Cod sursa (job #3345343)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1005;
vector<int> adj[NMAX];
int disc[NMAX], low[NMAX]; /// low - nivelul min la care se poate intoarce
stack<pair<int, int>> st;
set<int> comp[NMAX];
int bcc = 0; /// numarul de componente
void dfs(int nod, int dad)
{
disc[nod] = disc[dad] + 1;
low[nod] = disc[nod];
for(auto x : adj[nod])
{
if(x == dad)
continue;
if(disc[x])
low[nod] = min(low[nod], disc[x]); /// ne intoarcem in spate si actualizam low
else
{
/// Mergem in fata
st.push({nod, x});
dfs(x, nod);
low[nod] = min(low[nod], low[x]); /// cand mergem in fata actualizam low
if(low[x] >= disc[nod]) /// daca gasim un punct critic
{
bcc++;
while(!st.empty())
{
comp[bcc].insert(st.top().first);
comp[bcc].insert(st.top().second);
if(st.top().first == nod && st.top().second == x)
{
st.pop();
break;
}
st.pop();
}
}
}
}
}
int main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int t=1;
//cin>>t;
while(t--)
{
int n, m, a, b;
cin>>n>>m;
for(int i=0; i<m; i++)
{
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 0);
cout<<bcc<<'\n';
for(int i=1; i<=bcc; i++)
{
//cout<<i<<" ";
for(auto x : comp[i])
cout<<x<<" ";
cout<<'\n';
}
}
return 0;
}