Pagini recente » Cod sursa (job #973239) | Cod sursa (job #552364) | Cod sursa (job #2079431) | Cod sursa (job #713221) | Cod sursa (job #2153679)
#include <bits/stdc++.h>
#define NMAX 100005
#define pii pair <int, int>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M;
int nivel[NMAX], jumpBack[NMAX];
vector < vector <int> > rsp;
vector <int> v[NMAX], sol;
stack <pii> 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()
{
fin >> N >> M;
for (int i = 1; i <= M; i++)
{
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
DFS(1, 0);
fout << rsp.size() << "\n";
for (int i = 0; i < rsp.size(); i++)
{
for (int j = 0; j < rsp[i].size(); j++)
fout << rsp[i][j] << " ";
fout << "\n";
}
fin.close();
fout.close();
return 0;
}