Pagini recente » Cod sursa (job #1071482) | Cod sursa (job #500671) | Cod sursa (job #2666654) | Cod sursa (job #457520) | Cod sursa (job #2604708)
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int t[2][1000005],start[100005],tata[100005];
short int ap[100005];
int k;
void dfs(int j,int tatic)
{
bool r=false;
ap[j]=1;
tata[j]=tatic;
k=start[j];
while(t[0][k]!=0)
if(ap[t[0][k]]==0)
{
ap[t[0][k]]=1;
dfs(t[0][k],j);
r=true;
k=t[1][k];
}
else
k=t[1][k];
if(r==false&&tatic!=0)
dfs(tatic,tata[tatic]);
}
int main()
{
int n,m,o,i,j,nr=0;
fin>>n>>m;
k=0;
for(o=1;o<=m;o++)
{
k++;
fin>>i>>j;
t[0][k]=j;
t[1][k]=start[i];
start[i]=k;
k++;
t[0][k]=i;
t[1][k]=start[j];
start[j]=k;
}
for(o=1;o<=n;o++)
if(ap[o]==0)
{
nr++;
dfs(o,0);
}
fout<<nr;
return 0;
}