Pagini recente » Cod sursa (job #702577) | Cod sursa (job #1826369) | Cod sursa (job #312142) | Cod sursa (job #2809220) | Cod sursa (job #2199013)
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
int nivel[Nmax], jumpBack[Nmax];
vector < vector <int> > rsp;
vector <int> v[Nmax], sol;
stack <pair <int, int > > st;
void getComponent(int nod, int nxt)
{
int x, y;
do{
x = st.top().first;
y = st.top().second;
st.pop();
sol.push_back(x);
sol.push_back(y);
}while(nod != x || nxt != y);
sort(sol.begin(), sol.end());
sol.erase(unique(sol.begin(), sol.end()), sol.end());
rsp.push_back(sol);
sol.clear();
}
void DFS(int nod, int father)
{
nivel[nod] = nivel[father] + 1;
jumpBack[nod] = nivel[nod];
vector <int> :: iterator it;
for (it = v[nod].begin(); it != v[nod].end(); it++)
{
int nxt = *it;
if (nxt == father) continue;
if (!nivel[nxt])
{
st.push({nod, nxt});
DFS(nxt, nod);
jumpBack[nod] = min(jumpBack[nod], jumpBack[nxt]);
if (jumpBack[nxt] >= nivel[nod])
getComponent(nod, nxt);
}
else jumpBack[nod] = min(jumpBack[nod], nivel[nxt]);
}
}
int main()
{
f >> n >> m;
for ( int i = 1 ; i <= m ; i ++ )
{
int x, y;
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
DFS(1, 0);
g << rsp.size() << "\n";
for ( int i = 0 ; i < rsp.size() ; i ++ )
{
for ( int j = 0 ; j < rsp[i].size() ; j ++ )
g << rsp[i][j] << " ";
g << "\n";
}
f.close();
g.close();
return 0;
}