Pagini recente » Cod sursa (job #590178) | Cod sursa (job #797258) | Cod sursa (job #1082949) | Cod sursa (job #2339670) | Cod sursa (job #2493150)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int n, m, nivel[N], nivelMin[N];
bool viz[N];
stack < pair <int, int> > st;
vector <int> L[N];
vector < vector<int> > comp;
void findComp(int nod, int nextNod)
{
vector<int> C;
int firstNode, secondNode;
do
{
firstNode = st.top().first;
secondNode = st.top().second;
st.pop();
C.push_back(firstNode);
C.push_back(secondNode);
}while (firstNode != nod || secondNode != nextNod);
sort(C.begin(), C.end());
C.erase(unique(C.begin(), C.end()), C.end());
comp.push_back(C);
}
void DFS(int nod, int tata)
{
viz[nod] = 1;
nivel[nod] = nivel[tata] + 1;
nivelMin[nod] = nivel[nod];
for (auto nextNod : L[nod])
{
if (nextNod != tata)
{
if (viz[nextNod])
nivelMin[nod] = min(nivelMin[nod], nivel[nextNod]);
else
{
st.push(make_pair(nod, nextNod));
DFS(nextNod, nod);
nivelMin[nod] = min(nivelMin[nod], nivelMin[nextNod]);
if (nivelMin[nextNod] >= nivel[nod])
findComp(nod, nextNod);
}
}
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
fin >> a >> b;
L[a].push_back(b);
L[b].push_back(a);
}
DFS(1, 0);
fout << comp.size() << "\n";
for (unsigned i = 0; i < comp.size(); i++)
{
for (auto j : comp[i])
fout << j << " ";
fout << "\n";
}
return 0;
}