Cod sursa(job #2673233)

Utilizator Arsene_DenisaArsene Denisa Arsene_Denisa Data 16 noiembrie 2020 12:09:26
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int l[1000][1000], m[1000][1000], ok[1000];
int n, conv=0;
vector<int>v[1000001];

void rec(int x, int y) {
     l[x][y]=l[y][x]=1;
     ok[x]=ok[y]=1;
     v[conv].push_back(x);
     v[conv].push_back(y);
     for(int i=1;i<=n;i++) {
            if(m[x][i]==1 && l[x][i]==0) {
                    rec(x, i);
            rec(i, x);
            }
            if(m[y][i]==1 && l[y][i]==0) {
                    rec(y, i);
                    rec(i, y);
            }
     }
}

int main() {
    int i, cs, j, a, b, r;
    char p;
    fin>>n>>r;
    /*
    cin.get(p);
    cin.get(p);
{1}
    while(p!=EOF && p!='\n') {
            a=0;
            b=0;
            while(p>='0' && p<='9') {
                    a=a*10+(p-'0');
                        cin.get(p);
            }
        cin.get(p);
        while(p!=EOF && p!='\n') {
            b=b*10+(p-'0');
            cin.get(p);
        }
        if(p=='\n') {
                cin.get(p);
        }
         m[a][b]=m[b][a]=1;
    }
    */
    for(i=1;i<=r;i++) {
    fin>>a>>b;
    m[a][b]=m[b][a]=1;
    }

    for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
              if(m[i][j]==1 && l[i][j]==0) {
                  conv++;
               rec(i, j);

              }
            }
    }
    for(i=1;i<=conv;i++) {
            sort(v[i].begin(), v[i].end());
    }
    for(i=1;i<=n;i++) {
            if(ok[i]==0) {
                    conv++;
            v[conv].push_back(i);
            }
    }
       fout<<conv<<"\n";
   /* sort(v+1, v+conv+1);
    for(i=1;i<=conv;i++) {
            int nn=v[i].size();
            for(j=0;j<nn;j++) {
                if(v[i][j]!=v[i][j+1] || j==nn-1) {
                        cout<<v[i][j]<<" ";
                }
            }
               cout<<"\n";
    }*/
    return 0;
}