Pagini recente » Cod sursa (job #2196067) | Cod sursa (job #556121) | Cod sursa (job #467754) | Cod sursa (job #3187627) | Cod sursa (job #988425)
Cod sursa(job #988425)
#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>
#define SIZE 100001
using namespace std;
int n, m, i, j, x, y, nr;
vector <int> adj[SIZE], dfn, low;
stack < pair <int, int> > st;
set <int> sol[SIZE];
void calc_sol(int father_node, int node)
{
++nr;
do
{
x=st.top().first; y=st.top().second;
sol[nr].insert(x); sol[nr].insert(y);
st.pop();
} while(x!=father_node || y!=node);
}
void DFS(int node, int num)
{
low[node]=dfn[node]=num;
for(vector <int> :: iterator it=adj[node].begin(); it!=adj[node].end(); ++it)
if(dfn[*it]==-1)
{
st.push(make_pair(node, *it));
DFS(*it, num+1);
low[node]=min(low[node], low[*it]);
if(low[*it]>=dfn[node])
calc_sol(node, *it);
}
else
low[node]=min(low[node], dfn[*it]);
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
while(m--)
{
scanf("%d %d", &x, &y);
adj[x].push_back(y);
adj[y].push_back(x);
}
dfn.resize(n+1); dfn.assign(n+1, -1);
low.resize(n+1);
DFS(1, 0);
printf("%d\n", nr);
for(i=1;i<=nr;++i)
{
for(set <int> :: iterator it=sol[i].begin(); it!=sol[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
return 0;
}