Pagini recente » Cod sursa (job #3285129) | Cod sursa (job #63693) | Cod sursa (job #3205066) | Cod sursa (job #2262314) | Cod sursa (job #1389549)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
vector<int> v[200001], noduri[200001];
int culoare[200001], parinte[200001], nivel[200001], minim[200001], noduri2[200001];
char punct[200001];
stack<int> q;
int sursa, fii, x, y;
void DFS(int nod, int& k)
{
int i, info;
culoare[nod] = 1;
minim[nod] = nivel[nod];
for (i = 0; i < v[nod].size(); i++)
{
info = v[nod][i];
if(info != parinte[nod] && nivel[nod] > nivel[info])
{
q.push(info);
q.push(nod);
}
if(!culoare[info])
{
nivel[info] = nivel[nod] + 1;
parinte[info] = nod;
if(nod == sursa)
fii++;
DFS(info,k);
if(minim[nod] > minim[info])
minim[nod] = minim[info];
if(minim[info] >= nivel[nod])
{
do
{
x = q.top();
q.pop();
noduri[k].push_back(x);
y = q.top();
q.pop();
noduri[k].push_back(y);
}
while((x != nod || y != info) && (x != info || y != nod));
k++;
}
}
else
if(minim[info] != parinte[nod] && minim[nod] > nivel[info])
minim[nod] = nivel[info];
}
}
int main()
{
int n, m, i, j, x, y, max, k = 0;
ifstream f("biconex.in");
ofstream g("biconex.out");
f >> n >> m;
for (i = 0; i < m; i++)
{
f >> x >> y;
v[y].push_back(x);
v[x].push_back(y);
}
for(i = 1; i <= n; i++)
if(!culoare[i])
{
nivel[i] = 1;
sursa = i;
fii = 0;
DFS(i,k);
punct[sursa] = fii > 1;
}
g << k << endl;
for(i = 0; i < k; i++)
{
max = 0;
for(j = 0; j < noduri[i].size(); j++)
{
noduri2[noduri[i][j]]++;
if(noduri[i][j] > max)
max = noduri[i][j];
}
for(j = 1; j <= max; j++)
if(noduri2[j])
{
g << j << " ";
noduri2[j] = 0;
}
g << endl;
}
return 0;
}