Pagini recente » Cod sursa (job #20715) | Cod sursa (job #2279392) | Cod sursa (job #284265) | Cod sursa (job #1866725) | Cod sursa (job #1768200)
#include <bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define show(x) cerr << #x << " = " << x << "\n";
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100005;
int n,m,nr,fat[NMAX],niv[NMAX],nivmin[NMAX];
bool art[NMAX];
vector<int>v[NMAX],t[NMAX],comp[NMAX];
bitset<NMAX>viz;
void Dfs(int x)
{
viz[x] = 1;
niv[x] = niv[fat[x]] + 1;
for (auto it : v[x])
if (!viz[it])
{
fat[it] = x;
t[x].pb(it);
Dfs(it);
}
//check if it's articulation point
int mn = 1<<30;
for (auto it : t[x])
mn = min(mn , nivmin[it]);
if (t[x].size() && mn >= niv[x]) art[x] = 1;
mn = min(mn , niv[x] - 1);
for (auto it : v[x])
if (niv[it] < niv[x])
mn = min(mn , niv[it]);
nivmin[x] = mn;
}
void Go(int x)
{
comp[nr].pb(x);
if (art[x] == 0)
for (auto it : t[x])
Go(it);
}
void Fill(int x)
{
for (auto it : t[x])
{
nr++; comp[nr].pb(x);
Go(it);
}
}
int main()
{
int i, x, y;
fin >> n >> m;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
v[x].pb(y);
v[y].pb(x);
}
Dfs(1);
if (t[1].size() > 1) art[1] = 1;
for (i = 1; i <= n; i++)
if (i == 1 || art[i] == 1)
Fill(i);
for (i = 1; i <= nr; i++)
{
for (auto it : comp[i])
fout << it << " ";
fout << "\n";
}
return 0;
}