Pagini recente » Cod sursa (job #2176398) | Cod sursa (job #1062316) | Cod sursa (job #1739178) | Cod sursa (job #497) | Cod sursa (job #419503)
Cod sursa(job #419503)
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
using namespace std;
#define NMAX 100005
#define min(a,b) (a<b?a:b)
int depth[NMAX], low[NMAX];
vector <int> G[NMAX];
stack < pair <int, int> > S;
vector < vector <int> > rez;
int n, cate;
void makeComp(int x, int y)
{
int ax, ay;
vector <int> Aux;
do
{
ax = S.top().first;
ay = S.top().second;
S.pop();
Aux.push_back(ax);
Aux.push_back(ay);
} while (ax != x || ay != y);
sort(Aux.begin(), Aux.end());
vector<int>::iterator it = unique(Aux.begin(), Aux.end());
Aux.resize( it - Aux.begin());
rez.push_back(Aux);
}
void df(int nod, int parent, int adanc)
{
depth[nod] = low[nod] = adanc;
vector<int>::iterator it;
for(it = G[nod].begin(); it != G[nod].end(); ++it)
{
if (*it == parent) continue;
if (depth[*it] == -1)
{
S.push(make_pair(nod, *it));
df(*it, nod, adanc+1);
low[nod] = min(low[nod], low[*it]);
if ( low[*it] >= depth[nod])
makeComp(nod, *it);
} else {
low[nod] = min(low[nod], low[*it]);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int mm;
scanf("%d %d ", &n, &mm);
for (;mm;--mm)
{
int x,y;
scanf("%d %d ", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= n; ++i) depth[i] = -1;
df(1,0,0);
cate = rez.size();
printf("%d\n", cate);
for (int i = 0; i < cate; ++i)
{
for (vector<int>::iterator it = rez[i].begin(); it != rez[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
}