Cod sursa(job #2420430)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 11 mai 2019 21:37:03
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#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";
  }//*/
}