Cod sursa(job #2667413)

Utilizator GeoDinBacauTofan George GeoDinBacau Data 3 noiembrie 2020 14:04:00
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("dfs.in");
ofstream fcout("dfs.out");

vector<int>nod[100003];
int n,m,x,y,nrconexe;
bool ap[110];

void dfs(int k)
{
    if(ap[k])
        return;
    ap[k]=1;
    for(int i=0;i<nod[k].size();i++)
        dfs(nod[k][i]);
}

int main()
{
    fcin>>n>>m;
    for(int i=1;i<=m;i++){
        fcin>>x>>y;
        nod[x].push_back(y);
        nod[y].push_back(x);
    }

    for(int i=1;i<=n;i++){
        if(ap[i])
            continue;
        nrconexe++;
        dfs(i);
    }

    fcout<<nrconexe;

    return 0;
}

//vector<int>nod[110];
//queue<int>coada;
//int n,m,x;
//bool ap[110];
//
//void gol_ap()
//{
//    for(int i=0;i<=110;i++)
//        ap[i]=0;
//    cout<<endl;
//}
//
//void afisqueue()
//{
//    queue<int>af;
//    af=coada;
//    cout<<'c'<<'-';
//    while(!af.empty()){
//        cout<<af.front()<<' ';
//        af.pop();
//    }
//    cout<<endl;
//}
//
//void DFS(int k)
//{
//    if(ap[k])
//        return;
//    cout<<k<<' ';
//    ap[k]=1;
//    for(int i=0;i<nod[k].size();i++)
//        DFS(nod[k][i]);
//}
//
//void BFS(int a)
//{
//    if(a==0)
//        return;
//    int b=0,c;
//    //cout<<endl<<"nrel-"<<a<<endl;
//    for(int i=1;i<=a;i++){
//        c=coada.front();
//        if(!ap[c]){
//            ap[c]=1;
//            cout<<c<<' ';
//            for(int j=0;j<nod[c].size();j++){
//                if(!ap[nod[c][j]]){
//                    coada.push(nod[c][j]);
//                    b++;
//                }
//            }
//        }
//        coada.pop();
//    }
//    BFS(b);
//}
//
//int main()
//{
//    fcin>>n>>m>>x;
//    int a,b;
//    for(int i=1;i<=m;i++){
//        fcin>>a>>b;
//        nod[a].push_back(b);
//        nod[b].push_back(a); //graf neorientat
//    }
//
//    for(int i=1;i<=n;i++)
//        sort(nod[i].begin(),nod[i].end());
//
//    DFS(x);
//    gol_ap();
//    coada.push(x);
//    BFS(1);
//    return 0;
//}

//    for(int i=1;i<=n;i++)
//        cout<<i<<": "<<nod[i].size()<<endl;

//    for(int i=1;i<=n;i++){
//        cout<<i<<": ";
//        for(int j=0;j<nod[i].size();j++)
//            cout<<nod[i][j]<<' ';
//        cout<<endl;
//    }