Cod sursa(job #2418701)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 5 mai 2019 20:21:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <stack>
#include <vector>
FILE * fin= fopen("dfs.in","r");
FILE * fout= fopen("dfs.out","w");

std::stack<int> s;
std::vector<int> v[100050];
int t[100050];
bool vis[100050];
int n,m;
int countt;
int main()
{
  fscanf(fin,"%d %d",&n,&m);
  for(int i=0;i<m;i++)
  {
    int j,k;
    fscanf(fin,"%d %d",&j,&k);
    v[j].push_back(k);
    v[k].push_back(j);
  }
  for(int i=1;i<=n;i++)
  {
    if(vis[i])continue;
    countt++;
    vis[i]=true;
    s.push(i);
    while(!s.empty())
    {
      int tp = s.top();
      int j=t[tp];
      for(;j<v[tp].size();j++)
      {
        t[tp]=j+1;
        int elem = v[tp][j];
        if(!vis[elem])
        {
          vis[elem]=true;
          s.push(elem);
          break;
        }
      }
      if(j==v[tp].size()) s.pop();
    }
  }
  fprintf(fout,"%d",countt);
}