Pagini recente » Cod sursa (job #1845056) | Cod sursa (job #1128048) | Cod sursa (job #232571) | Cod sursa (job #1729231) | Cod sursa (job #2382830)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");
const int NMAX = 1e5 + 5;
int n, m;
vector <int> G[NMAX];
int p[NMAX], niv[NMAX], sus[NMAX];
vector <int> dob[2 * NMAX];
int nrComp;
void dfsStart(int nod)
{
sus[nod] = NMAX;
for (auto v: G[nod])
if (!niv[v]) // fiu
{
niv[v] = niv[nod] + 1;
p[v] = nod;
dfsStart(v);
sus[nod] = min(sus[nod], sus[v]);
}
else if (v != p[nod]) // muchie de intoarcere
sus[nod] = min(sus[nod], niv[v]);
}
void dfs(int nod, int comp)
{
//if (nod == 7)
//cout << comp;
for (auto v: G[nod])
if (p[v] == nod) // fiu
{
if (sus[v] < niv[nod] || (dob[comp].size() == 1 && sus[v] == niv[nod])) // poate merge mai sus; il bagam in componenta asta
{
dob[comp].push_back(v);
dfs(v, comp);
}
else // nu poate merge mai sus; incep componenta noua cu tatal si fiul in ea
{
nrComp++;
dob[nrComp].push_back(nod);
dob[nrComp].push_back(v);
dfs(v, nrComp);
}
}
}
int main()
{
fi >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
fi >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
niv[1] = 1;
dfsStart(1);
/*for (int i = 1; i <= n; i++)
cout << i << ": " << sus[i] << "\n";*/
//return 0;
nrComp = 1;
dob[1].push_back(1);
dfs(1, 1);
fo << nrComp << "\n";
for (int i = 1; i <= nrComp; i++)
{
for (auto x: dob[i])
fo << x << " ";
fo << "\n";
}
return 0;
}