Pagini recente » Cod sursa (job #1756734) | Cod sursa (job #1583734) | Cod sursa (job #809397) | Cod sursa (job #2928174) | Cod sursa (job #726452)
Cod sursa(job #726452)
#include<iostream>
#include<fstream>
#include<stack>
using namespace std;
#define max 100005
struct lista{
unsigned long int vec;
lista *next;
};
ifstream f("dfs.in");
ofstream g("dfs.out");
stack <unsigned long int> stiva;
unsigned long int m,viz[max]={0},k;
lista *v[max];
void citire(unsigned long int &n){
f>>n>>m;
for(unsigned long int i=1;i<=n;i++)
v[i]=NULL;
for(unsigned long int i=1;i<=m;i++){
unsigned long int x,y;
f>>x>>y;
if(v[x]==NULL){
v[x]=new lista;
v[x]->vec=y;
v[x]->next=NULL;
}
else{
lista *p=new lista;
p->vec=y;
p->next=v[x];
v[x]=p;
}
}
}
unsigned long int nevizitat(unsigned long int n){
unsigned long int i=k+1;
while(i<=n)
if(viz[i]==0)
return i;
else
i++;
return 0;
}
unsigned long int componente_conexe(unsigned long int n){
unsigned long int nr=0;
lista *p;
while(k=nevizitat(n)){
//unsigned long int i=nevizitat(n,viz);
p=v[k];
stiva.push(k);
viz[k]=1;
while(v[k]!=NULL){
if(viz[v[k]->vec]==0){
stiva.push(v[k]->vec);
viz[v[k]->vec]=1;
int t=v[k]->vec;
v[k]=v[k]->next;
k=t;
}
else
v[k]=v[k]->next;
if(v[k]==NULL&&!stiva.empty()){
stiva.pop();
if(!stiva.empty())
v[k]=v[stiva.top()];
}
}
nr++;
}
return nr;
}
int main(){
unsigned long int n;
citire(n);
g<<componente_conexe(n)<<endl;
}