Mai intai trebuie sa te autentifici.
Cod sursa(job #1900376)
Utilizator | Data | 3 martie 2017 12:39:18 | |
---|---|---|---|
Problema | Componente biconexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.61 kb |
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
vector < set < int > > sol; // componentele biconexe
stack < pair < int, int > > stk; // stiva muchi
vector < int > a[NMAX]; // matricea de adiacenta
int low[NMAX], dfn[NMAX], n, m;
void BiconexComponent(int x, int y)
{
set < int > aux;
int a, b;
do
{
a = stk.top().first;
b = stk.top().second;
stk.pop();
//aux.push_back(a);
//if (aux.find(a) == aux.end())
aux.insert(a);
//if (aux.find(b) == aux.end())
aux.insert(b);
} while (a != x || b != y);
sol.push_back(aux);
}
void df(int nod, int precNod)
{
low[nod] = dfn[nod] = dfn[precNod] + 1;
for (unsigned i = 0; i < a[nod].size(); i++)
{
int next = a[nod][i];
if (next == nod) continue;
if (!dfn[next])
{
stk.push(make_pair(nod, next));
df(next, nod);
low[nod] = min(low[nod], low[next]);
if (low[next] >= dfn[nod])
BiconexComponent(nod, next);
}
else low[nod] = min(low[nod], dfn[next]);
}
}
int main()
{
f>>n>>m;
while (m--)
{
int x, y;
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
df(1, 0);
g<<sol.size()<<'\n';
for (int i = 0; i < sol.size(); i++)
{
set < int >::iterator it;
for (it = sol[i].begin(); it != sol[i].end(); it++)
g<<* it<<' ';
g<<'\n';
}
return 0;
}