Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- ifstream fin("componenteconexe2.in");
- ofstream fout("componenteconexe2.out");
- struct nod{
- int valoare;
- nod *urmator;
- }*prim[100001];
- long long n,m,coada[100001],vizitat[100001],c;
- void adaugare_in_lista(nod *&prim,long long x)
- {
- nod *q = new nod;
- q->valoare = x;
- q->urmator = prim;
- prim = q;
- }
- void citire()
- {
- fin>>n;
- long long i,x,y;
- while(fin>>x>>y)
- {
- adaugare_in_lista(prim[x],y);
- adaugare_in_lista(prim[y],x);
- m++;
- }
- }
- void BFS(long long nod_start,long long &componenta_conexa)
- {
- long long p,u,i,x;
- p=u=0;
- vizitat[nod_start] = componenta_conexa;
- coada[u] = nod_start;
- while(p<=u)
- {
- x = coada[p++];
- for(nod *q = prim[x];q;q=q->urmator)
- if(vizitat[q->valoare] == 0)
- {
- coada[++u] = q->valoare;
- vizitat[q->valoare] = componenta_conexa;
- }
- }
- m = m-u;
- }
- int main()
- {
- citire();
- long long componenta_conexa ,i;
- componenta_conexa = 0;
- for(i=1;i<=n;i++)
- if(vizitat[i]==0)
- {
- componenta_conexa = componenta_conexa + 1;
- BFS(i,componenta_conexa);
- }
- fout<<m;
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement