Pagini recente » Cod sursa (job #609494) | Cod sursa (job #832460) | Cod sursa (job #2063958) | Cod sursa (job #2266674) | Cod sursa (job #1412495)
#include <fstream>
#include <vector>
#include <bitset>
#include <set>
#include <stack>
#define per pair<int,int>
#define mper make_pair
#define x first
#define y second
#define nmax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m;
int low[nmax],cbc;
vector <int> v[nmax];//Liste de adiacenta
bitset <nmax> uz;
set <int> r[nmax];//Solutiile biconexe
set <int> :: iterator it;
stack <per> s;
per p;
//Fac dfs pentru un nod retinand nivelul si tatal nodului
void dfs(int nod,int niv,int tata)
{
uz[nod]=1;
low[nod]=niv;
int i,fiu;
for (i=0;i<v[nod].size();i++) {
fiu=v[nod][i];
//Iterez pentru fiecare fiu
if (fiu==tata)
continue;
//Am grija sa nu ma intorc in tata
if (uz[fiu]==0) {
//Daca nu s-a mai ajuns in fiu
s.push(mper(nod,fiu));
dfs(fiu,niv+1,nod);
low[nod]=min(low[nod],low[fiu]);
//Actualizez vectorul low
if (low[fiu]>=niv) {
//Construiesc componenta biconexa noua
cbc++;
do {
p=s.top();
s.pop();
r[cbc].insert(p.x);
r[cbc].insert(p.y);
} while ((nod!=p.x||fiu!=p.y));
}
}
else
low[nod]=min(low[nod],low[fiu]);
}
}
int main()
{
int i,j,a,b;
f>>n>>m;
for (i=1;i<=m;i++) {
f>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
//Creez graful
}
for (i=1;i<=n;i++)
if (!uz[i])
dfs(i,1,0);
//Parcurg componentele conexe
g<<cbc<<'\n';
for (i=1;i<=cbc;i++) {
for (it=r[i].begin();it!=r[i].end();it++)
g<<*it<<' ';
g<<'\n';
}
return 0;
}