Pagini recente » Cod sursa (job #2492498) | Cod sursa (job #2826341) | Cod sursa (job #1325730) | Cod sursa (job #87942) | Cod sursa (job #2420430)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
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];
std::stack<int> s;
int root[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);
}
rez=std::vector<std::vector<int> >();
for(int i=1;i<=n;i++)
{
if(vis[i])continue;
vis[i]=true;
s.push(i);
ins[i]=true;
while(!s.empty())
{
int tp =s.top();
int j;
for(j=t[tp];j<v[tp].size();j++)
{
t[tp]=j+1;
int elem = v[tp][j];
if(ins[elem] && root[tp]!=elem)
{
rcount++;
rez.push_back(std::vector<int>());
while(s.top()!=elem)
{
ins[s.top()]=false;
rez[rcount-1].push_back(s.top());
s.pop();
}
rez[rcount-1].push_back(s.top());
s.push(tp);
break;
}
if(!vis[elem])
{
vis[elem]=true;
ins[elem]=true;
root[elem]=tp;
s.push(elem);
break;
}
}
if(j==v[tp].size())
{
ins[tp]=false;
s.pop();
if(!s.empty() && root[tp]==s.top())
{
rcount++;
rez.push_back(std::vector<int>());
rez[rcount-1].push_back(s.top());
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";
}//*/
}