Pagini recente » Cod sursa (job #2031218) | Cod sursa (job #1916117) | Cod sursa (job #436566) | Cod sursa (job #1825151) | Cod sursa (job #1303011)
#include <fstream>
using namespace std;
ifstream x ("dfs.in");
ofstream y ("dfs.out");
struct node
{
int i;
node *next;
};
int n,m;
int a[100001];
node *temp;
node *current;
node *head[100001];
void add(int X, int Y)
{
if(head[X]==NULL)
{
head[X]=new node();
head[X]->i=Y;
head[X]->next=NULL;
}
else
{
current=new node();
current=head[X];
while(current->next)
current=current->next;
temp=new node();
temp->i=Y;
temp->next=NULL;
current->next=temp;
}
}
void dfs(int i, int k)
{
a[i]=k;
if(head[i])
{
node *current;
current=head[i];
while(current)
{
if(a[current->i]==0)
dfs(current->i,k);
current=current->next;
}
}
}
int main()
{
int i;
x>>n>>m;
int X,Y;
for(i=1;i<=m;i++)
{
x>>X>>Y;
add(X,Y);
add(Y,X);
}
/*
for(i=1;i<=n;i++)
{
y<<i<<" --> ";
current=head[i];
while(current)
{
y<<current->i<<' ';
current=current->next;
}
y<<'\n';
}
y<<'\n';
*/
int k=0;
for(i=1;i<=n;i++)
if(a[i]==0)
{
k++;
dfs(i,k);
}
y<<k<<'\n';
/*
for(i=1;i<=n;i++)
y<<a[i]<<' ';
y<<'\n';
*/
return 0;
}