Cod sursa(job #2346670)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 17 februarie 2019 22:26:21
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> g[NMAX],rez[NMAX];
stack <int> Q;
int viz[NMAX],index[NMAX],lowlink[NMAX];
int N,M,k,cnt;
void citire();
void afisare();
void DFS(int nod);
int main()
{int nr,x,i,j;
    citire();
    for(i=1;i<=N;i++)
        if(!viz[i])
          {nr=g[i].size();
           for(j=0;j<nr;j++)
              {
               x=g[i][j];
               viz[x]=1;
               DFS(x);
              }
          }
    afisare();
    return 0;
}
void citire()
{int i,ei,ef;
    fin>>N>>M;
    for(i=1;i<=M;i++)
       {
        fin>>ei>>ef;
        g[ei].push_back(ef);
       }
}
void DFS(int nod)
{int x;
 vector <int>::iterator it;
    Q.push(nod);
    index[nod]=++k;
    lowlink[nod]=k;
    for(it=g[nod].begin(); it!=g[nod].end(); it++)
         {
          if(!viz[*it])
            {
             viz[*it]=1;
             DFS(*it);
            }
          lowlink[nod]=min(lowlink[nod],lowlink[*it]);
         }
    if(index[nod]==lowlink[nod])
      {
        cnt++;
        do
        {
         x=Q.top();
         Q.pop();
         rez[cnt].push_back(x);
        }
        while (nod!=x);
      }

}
void afisare()
{
    int i;
    fout<<cnt<<'\n';
    vector <int>::iterator it;
    for(i=1; i<=cnt; i++)
    {
        for(it=rez[i].begin(); it!=rez[i].end(); it++)
            fout<<*it<<' ';
        fout<<'\n';
    }
}