Pagini recente » Cod sursa (job #2479492) | Cod sursa (job #1483683) | Cod sursa (job #45105) | Cod sursa (job #2063308) | Cod sursa (job #1368354)
#include <algorithm>
#include <fstream>
#include <stack>
#include <vector>
#define N 100001
#define M 200001
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
struct muchie
{
int x, y;
};
int vf[2 * M], urm[2 * M], lst[N], nr = 0;
int n, m;
int t[N], l[N], niv[N];
bool ok[N];
vector<int> componente[N];
stack<muchie> s;
int nrc = 0;
void df(int x)
{
ok[x] = 1;
l[x] = niv[x];
for(int p = lst[x]; p; p = urm[p])
{
int y = vf[p];
if(!ok[y])
{
s.push((muchie){x, y});
t[y] = x;
niv[y] = niv[x] + 1;
df(y);
if(l[y] < l[x])
l[x] = l[y];
if(l[y] >= niv[x])
{
//pct de articulatie
nrc++;
int x1, y1;
do
{
muchie m = s.top();
s.pop();
x1 = m.x;
y1 = m.y;
componente[nrc].push_back(x1);
componente[nrc].push_back(y1);
}while(x1 != x && y1 != y);
}
}
else if(y != t[x] && niv[y] < l[x])
{
//muchie de intoarcere
l[x] = niv[y];
}
}
}
void adauga_muchie(int x, int y)
{
vf[++nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
vf[++nr] = x;
urm[nr] = lst[y];
lst[y] = nr;
}
void citire()
{
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
adauga_muchie(x, y);
}
}
void afisare()
{
out << nrc << '\n';
for(int i = 1; i <= nrc; i++)
{
sort(componente[i].begin(), componente[i].end());
componente[i].erase(unique(componente[i].begin(), componente[i].end()), componente[i].end());
for(size_t j = 0; j < componente[i].size(); j++)
out << componente[i][j] << ' ';
out << '\n';
}
}
int main()
{
citire();
for(int i = 1; i <= n; i++)
if(!ok[i])
df(i);
afisare();
return 0;
}