Cod sursa(job #1132122)

Utilizator Dayanna000Amegica Dayanna Dayanna000 Data 2 martie 2014 18:26:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define nr 100001
vector <int> v[nr],comp[nr];
stack <int> S;
bool in_stack[nr];
int index[nr],low_link[nr],poz=0,ix=0;
void tarjan(int x)
  {
     index[x]=ix;
     low_link[x]=ix;
     in_stack[x]=1;
     ix++;
     S.push(x);
     for(int l=0;l<v[x].size();++l)
       if(index[v[x][l]]==-1)
          {
             tarjan(v[x][l]);
             low_link[x]=min(low_link[x],low_link[v[x][l]]);
          }
       else
       if(in_stack[v[x][l]]==1)
          low_link[x]=min(low_link[x],index[v[x][l]]);
     if(low_link[x]==index[x])
        {
          int w;
          do
            {
               w=S.top();
               S.pop();
               in_stack[w]=0;
               comp[poz].push_back(w);
            }
          while(w!=x);
          poz++;
        }
  }
int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n,m,i,xx,y;
    f>>n>>m;
    for(i=1;i<=m;++i)
      {
        f>>xx>>y;
        v[xx].push_back(y);
      }
    for(i=1;i<=n;++i)
      {
        index[i]=-1;
        in_stack[i]=0;
      }
    for(i=1;i<=n;++i)
      if(index[i]==-1)
         tarjan(i);
    g<<poz<<'\n';
    for(i=0;i<poz;++i)
      {
        for(int j=0;j<comp[i].size();++j)
          g<<comp[i][j]<<"  ";
        g<<'\n';
      }
    f.close();
    g.close();
    return 0;
}