Cod sursa(job #2194148)

Utilizator dobrandreiAndrei Dobra dobrandrei Data 12 aprilie 2018 14:46:47
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>

using namespace std;
FILE *f,*g;

int n,m;
int start[100002],t[2][400002];
bool been[100002];
void ways()
{
  int x,y,k=0;
  for(int i=1;i<=m;i++)
  {
    fscanf(f,"%d %d",&x,&y);
    k++;
    t[0][k]=y;
    t[1][k]=start[x];
    start[x]=k;

    k++;
    t[0][k]=x;
    t[1][k]=start[y];
    start[y]=k;
  }
}

void dfs(int node)
{
  been[node]=1;
  int poz=start[node];
  while(poz)
  {
    if(!been[t[0][poz]])
      dfs[t[0][poz]],been[t[0][poz]]=1;
    poz=t[1][poz];
  }
}

int main()
{
    f=fopen("dfs.in","r");
    g=fopen("dfs.out","w");
    fscanf(f,"%d %d",&n,&m);
    int nr=0;
    ways();
    for(int i=1;i<=n;i++)
    {
      if(!been[i])
        dfs(i),nr++;
    }
    fprintf(g,"%d",nr);
    return 0;
}