Pagini recente » Cod sursa (job #2300372) | Cod sursa (job #2159247) | Cod sursa (job #2550453) | Cod sursa (job #43630) | Cod sursa (job #2420439)
#include <iostream>
#include <fstream>
#include <vector>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
int n,m;
std::vector<int> v[100500];
std::vector<std::vector<int> > rez;
int rcount;
bool vis[100500];
bool ins[100500];
int t[100500];
int pos;
int s[100500];
int root[100500];
int id[100500];
int main()
{
fin>>n>>m;
for(int i=0;i<m;i++)
{
int j,k;
fin>>j>>k;
v[j].push_back(k);
v[k].push_back(j);
}
for(int i=1;i<=n;i++)
id[i]=i;
rez=std::vector<std::vector<int> >();
for(int i=1;i<=n;i++)
{
if(vis[i])continue;
vis[i]=true;
s[0]=i;
ins[i]=true;
while(pos!=-1)
{
int tp =s[pos];
// std::cout<<tp<<": \n";
int j;
for(j=t[tp];j<v[tp].size();j++)
{
t[tp]=j+1;
int elem = v[tp][j];
// std::cout<<elem<<" ";
if(ins[elem] && root[tp]!=elem)
{
rcount++;
rez.push_back(std::vector<int>());
int place= pos;
while(s[place]!=elem)
{
ins[s[place]]=false;
rez[rcount-1].push_back(s[place]);
id[s[place]]=elem;
// std::cout<<"deleting: "<<s[place]<<"\n";
place--;
}
rez[rcount-1].push_back(elem);
break;
}
if(!vis[elem])
{
vis[elem]=true;
ins[elem]=true;
root[elem]=tp;
pos++;
s[pos]=elem;
break;
}
}
if(j==v[tp].size())
{
ins[tp]=false;
pos--;
if(pos>=0 && root[tp]==s[pos]&&id[tp]!=id[s[pos]])
{
rcount++;
rez.push_back(std::vector<int>());
rez[rcount-1].push_back(s[pos]);
rez[rcount-1].push_back(tp);
}
}
}//*/
}
fout<<rez.size()<<'\n';
for(int i=0;i<rez.size();i++)
{
for(int j=0;j<rez[i].size();j++)
fout<< rez[i][j]<<" ";
fout<<"\n";
}//*/
}