Pagini recente » Cod sursa (job #1682081) | Cod sursa (job #1551378) | Cod sursa (job #2384557) | Cod sursa (job #759726) | Cod sursa (job #1302932)
#include <fstream>
using namespace std;
ifstream x ("dfs.in");
ofstream y ("dfs.out");
struct node
{
int i;
node *next;
};
int n,m;
int k;
int a[100010];
node *current;
node *temp;
node *head[100010];
void dfs(int i)
{
a[i]=k;
if(head[i])
{
current=head[i];
while(current)
{
dfs(current->i);
current=current->next;
}
}
}
int main()
{
int i;
x>>n>>m;
int X,Y;
for(i=1;i<=m;i++)
{
x>>X>>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;
}
}
/*
for(i=1;i<=n;i++)
{
y<<i<<" --> ";
current=head[i];
while(current)
{
y<<current->i<<' ';
current=current->next;
}
y<<'\n';
}
y<<'\n';
*/
for(i=1;i<=n;i++)
if(a[i]==0)
{
k++;
dfs(i);
}
y<<k<<'\n';
/*
for(i=1;i<=n;i++)
y<<a[i]<<' ';
y<<'\n';
*/
return 0;
}