Cod sursa(job #2742959)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 22 aprilie 2021 13:09:10
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

ifstream cin ("dfs.in") ;
ofstream cout ("dfs.out") ;

/*
graf theory
graf complet -> toate nodurile sunt legate intre ele
graf bipartit -> nodurile sunt impartite in cel putin doua multimi care nu au legaturi
graf conex(legat) -> se poate ajunge de la orice varf la oricare al varg in cel putin o modalitate
componenta conexa -> subgraf conex maximal
graf puternic conex -> se refera doar la grafuri orientate unde doua noduri pot fi legate dar nu se poate ajunge la un nod de la altul
deci graful puternic conex este graful orientat in care se poate ajunge de la orice nod la oricare alt nod

graf hamiltonian :

graf care are un ciclu hamiltonian
ciclu hamiltonian : ciclu care trece prin fiecare nod al grafului exact o data

graf eulian :

graf care are un ciclu eulerian :
ciclu eulerian : ciclu care trece prin fiecare nod al grafului cel putin o data

este eulerian daca si numai daca orice grad al vreunui nod este par

matematica :

cate grafuri neorientate cu n noduri exista :
2^(n*(n-1)/2)

cate grafuri orientate cu n noduri exista :


cate grafuri partiale are un graf cu n muchii :


cate muchii are un graf neorientat complet :


cate muchii are un graf bipartit complet :

cate grafuri orientate complete cu n noduri :



*/

///int m[109][109], viz[109] ;

vector<int> G[100009] ;

int viz[100009] ;

void fil(int x)
{

    for(int f = 0 ; f < G[x].size() ; f ++)
        if(!viz[G[x][f]])viz[G[x][f]] = 1, fil[G[x][f]] ;

}

int main()
{
    int n, mm, x ;

    cin >> n >> mm ;

    for(int f = 1, a, b ; f <= mm ; f ++)
        cin >> a >> b, G[a].push_back(b), G[b].push_back(a) ;

    int l = 0 ;

    for(int f = 1 ; f <= n ; f ++)
        if(!viz[f])l ++, fil(f) ;

    cout << l ;

    return 0;
}