Pagini recente » Cod sursa (job #528380) | Cod sursa (job #729102) | Cod sursa (job #940807) | Cod sursa (job #2901193) | Cod sursa (job #951460)
Cod sursa(job #951460)
#include <iostream>
#include<vector>
#include<stack>
#include<string>
#include<fstream>
#include<algorithm>
#define lim 100
using namespace std;
class biconex {
int n,m,sel[lim],t[lim],nr;
vector<int> v[lim],comp[lim];
stack<int> stiva;
fstream in,out;
public:
biconex(string fin, string fout)
{
in.open(fin.c_str(), ios::in);
out.open(fout.c_str(), ios::out);
nr=0;
}
~biconex()
{
in.close();
out.close();
}
void read()
{
int a,b;
in>>n>>m;
for(int i=1;i<=m;i++)
{
in>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
sel[i]=0;
}
}
int dfs(int nod,int niv)
{
sel[nod]=niv;
stiva.push(nod);
vector<int>::iterator it;
for(it=v[nod].begin();it<v[nod].end();it++)
{
int aux;
//cout<<*it<<endl;
if( *it == t[nod] ) continue;
if(sel[*it]==0)
{
stiva.push(nod);
t[*it]=nod;
//cout<<"*it: "<<*it<<", niv: "<<niv+1<<endl;
dfs(*it,niv+1);
if(sel[*it]>=niv)
{
while(stiva.top()!=nod)
{
comp[nr].push_back(stiva.top());
stiva.pop();
}
comp[nr].push_back(stiva.top());
sort(comp[nr].begin(), comp[nr].end());
nr++;
}
}
aux=sel[*it];
if(sel[nod]>aux)
{
sel[nod]=aux;
}
}
return sel[nod];
}
void solve()
{
for(int i=1;i<=n;i++)
{
if(sel[i]==0)
{
dfs(i,1);
}
}
vector<int>::iterator it;
out<<nr<<endl;
for(int i=0;i<nr;i++)
{
int sem=0;
for(it=comp[i].begin();it<comp[i].end();it++)
{
sem=0;
if(*it!=*(it+1))
{
sem=1;
}
if(sem==1)
{
out<<*it<<" ";
}
}
out<<endl;
}
}
};
int main()
{
biconex X("biconex.in","biconex.out");
X.read();
X.solve();
return 0;
}