Pagini recente » Cod sursa (job #740905) | Cod sursa (job #2891999) | Cod sursa (job #280523) | Cod sursa (job #2349007) | Cod sursa (job #2742959)
#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;
}