Cod sursa(job #2420439)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 11 mai 2019 22:32:57
Problema Componente biconexe Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#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";
  }//*/
}