Pagini recente » Cod sursa (job #1525016) | Cod sursa (job #2718378) | Cod sursa (job #1554677) | Cod sursa (job #2455070) | Cod sursa (job #3202383)
#include <fstream>
#include <vector>
#define ll long long
using namespace std;
const int NMAX = 1e5;
vector <int> g[NMAX + 1];
int low[NMAX + 1];
int enter[NMAX + 1];
bool art[NMAX + 1];
vector <pair <int, int> > cur;
vector <vector <int> > comps;
void compute_bcc(int nod, int parent)
{
comps.push_back(vector <int> ());
pair <int, int> ax = make_pair(nod, parent);
while (cur.back() != ax)
{
comps.back().push_back(cur.back().first);
cur.pop_back();
}
cur.pop_back();
comps.back().push_back(nod);
comps.back().push_back(parent);
}
int n;
void dfs(int nod, int parent)
{
cur.push_back({nod, parent});
static int time = 0;
enter[nod] = ++time;
low[nod] = enter[nod];
for (int x : g[nod])
{
if (enter[x] == 0)
{
dfs(x, nod);
if (low[x] == enter[nod])
{
if (nod == 1)
art[nod] |= (time != n);
else
art[nod] = 1;
if (art[nod] or nod == 1)
//1 este radacina, asadar facem ceva special, foarte profesionist
{
compute_bcc(x, nod);
}
}
low[nod] = min(low[nod], low[x]);
}
else
low[nod] = min(low[nod], enter[x]);
}
}
signed main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int m, i;
cin >> n >> m;
for (i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 0);
cout << comps.size() << "\n";
for (i = 0; i < comps.size(); i++, cout << "\n")
for (int x : comps[i])
cout << x << " ";
}