Cod sursa(job #2796396)

Utilizator andreea_07Andreea Georgescu andreea_07 Data 7 noiembrie 2021 23:39:59
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <fstream>


using namespace std;

int n,m,nrcomp,viz[100005];
stack <int> stiva;
vector <int> componente[100005],graf[100005],graf_t[100005];
ifstream fin("ctc.in");
ofstream fout("ctc.out");

void  dfs(int s)
{ int i;
  viz[s]=1;
  ///cout<<s<<" ";
 vector<int>::iterator it;
    for ( it = graf[s].begin(); it != graf[s].end(); ++it)
       if (!viz[*it]) dfs(*it);
    stiva.push(s);
}

void dfst(int s)
    {viz[s] = 2;
     componente[nrcomp].push_back(s);
 vector<int>::iterator it;
      for ( it = graf_t[s].begin(); it != graf_t[s].end(); ++it)
 if (viz[*it]==1) dfst(*it);

}



int main()
{
  int x,y;
   int nod;
   fin>>n>>m;
for(int i=1;i<=m;i++)
{

    fin>>x>>y;
    graf[x].push_back(y);
    graf_t[y].push_back(x);
}
   for(int i=1;i<=n;i++)
        if(!viz[i])
           dfs(i);
    /*for(int i=1;i<=n;i++)
            {int x=stiva.top();
             cout<<x<<" ";
               stiva.pop();}*/

    while(!stiva.empty())
        {
        nod = stiva.top();
       // cout << nod << " ";
        if (viz[nod] == 1)
        {
            nrcomp++;
            dfst(nod);
        }
        stiva.pop();
    }
    out<<nrcomp;
    fout<<"\n";
    for (int i=1;i<=nrcomp;i++)
   {
   for(vector<int>::iterator it1= componente[i].begin(); it1!= componente[i].end(); ++it1)
fout<<*it1 <<" ";
   fout<<"\n";}
    return 0;
}