Pagini recente » Cod sursa (job #1552103) | Cod sursa (job #2330014) | Cod sursa (job #2011378) | Cod sursa (job #1632543) | Cod sursa (job #726034)
Cod sursa(job #726034)
#include<iostream>
#include<fstream>
#include<stack>
using namespace std;
#define max 100001
struct lista{
int vec;
lista *next;
};
ifstream f("dfs.in");
ofstream g("dfs.out");
stack <int> stiva;
int m;
void citire(int &n, lista *v[max]){
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;
}
}
}
int nevizitat(int n,int viz[max]){
int i=1;
while(i<=n)
if(viz[i]==0)
return i;
else
i++;
return 0;
}
int componente_conexe(int n,lista *v[max],int viz[max]){
int nr=0;
lista *p;
while(nevizitat(n,viz)){
int i=nevizitat(n,viz);
p=v[i];
stiva.push(i);
viz[i]=1;
while(p!=NULL){
if(viz[p->vec]==0){
stiva.push(p->vec);
viz[p->vec]=1;
p=v[p->vec];
}
else
p=p->next;
if(p==NULL&&!stiva.empty()){
stiva.pop();
if(!stiva.empty())
p=v[stiva.top()];
}
}
nr++;
}
return nr;
}
int main(){
int n,viz[max]={0};
lista *v[max];
citire(n,v);
g<<componente_conexe(n,v,viz)<<endl;
}