Pagini recente » Cod sursa (job #978518) | Cod sursa (job #307654) | Cod sursa (job #708699) | Cod sursa (job #2970763) | Cod sursa (job #2927577)
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
#define MAX 100005
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,comp_con=0;
stack<int> stiva;
int vizitat[MAX];
vector<vector<int>> lista_adiacenta;
void lista_construire(){
int i,j,k;
for(i=0;i<m;i++){
f>>j>>k;
lista_adiacenta[j].push_back(k);
}
}
void lista_afisare(){
int i,j;
for(i=1;i<=n;i++){
cout<<i<<": ";
for(j=0;j<lista_adiacenta[i].size();j++)
cout<<lista_adiacenta[i][j]<<' ';
cout<<endl;
}
}
void dfs()
{
int i,j;
i=1;
while(i<=n)
{
if(vizitat[i]==1) i++;
else
{
vizitat[i]=1;
stiva.push(i);
while(!stiva.empty())
{
stiva.pop();
for(j=0;j<lista_adiacenta[i].size();j++)
{
if(vizitat[lista_adiacenta[i][j]]==0)
{stiva.push(lista_adiacenta[i][j]);
vizitat[lista_adiacenta[i][j]]=1;}
}
}
comp_con++;
i++;
}
}
g<<comp_con;
}
int main()
{
f>>n>>m;
lista_adiacenta.resize(n+1);
lista_construire();
for(int i=1;i<=n;i++)
vizitat[i]=0;
dfs();
}