Pagini recente » Cod sursa (job #872565) | Cod sursa (job #1846960) | Cod sursa (job #1340944) | Cod sursa (job #2626232) | Cod sursa (job #2663225)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector <int> l[100001];
int N, M, low[100001],nodet[100001];
int timp;
stack <pair <int, int> > st;
vector <vector <int> > sol;
void create_comp(int i, int j)
{
vector <int> new_comp;
int x,y;
do
{
x = st.top().first;
y = st.top().second;
st.pop();
new_comp.push_back(x);
new_comp.push_back(y);
} while (x != i || y != j);
sol.push_back(new_comp);
}
void DFS(int nod, int t)
{
nodet[nod] = timp;
low[nod] = timp;
for (int i = 0; i < l[nod].size(); i++)
{
if (l[nod][i] != t && nodet[l[nod][i]] == -1)
{
st.push({nod, l[nod][i]});
timp++;
DFS(l[nod][i], nod);
low[nod] = min(low[nod], low[l[nod][i]]);
if (nodet[nod] <= low[l[nod][i]])
{
create_comp(nod, l[nod][i]);
}
}
else if(nodet[l[nod][i]] != -1)
{
low[nod] = min(low[nod], nodet[l[nod][i]]);
}
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> N >> M;
int i,j,k;
for (i = 0; i < M; i++)
{
fin >> j >> k;
l[j].push_back(k);
l[k].push_back(j);
}
for (i = 1; i <= N; i++)
nodet[i] = -1;
DFS(1, 0);
fout << sol.size() << "\n";
for (i = 0; i < sol.size(); i++)
{
sort(sol[i].begin(), sol[i].end());
sol[i].erase(unique(sol[i].begin(), sol[i].end()), sol[i].end());
for (j = 0; j < sol[i].size(); j++)
fout << sol[i][j] << " ";
fout << "\n";
}
return 0;
}