Pagini recente » Cod sursa (job #445708) | Cod sursa (job #2325406) | the_wild_west | Cod sursa (job #1934682) | Cod sursa (job #2326636)
#include <fstream>
using namespace std;
ofstream out("dfs.out");
ifstream in("dfs.in");
ifstream file("dfs.in");
long v[100001], cd[100001], v1[100001], com[100001], componente;
long *c[100001];
long var, n;
void dfs(int nod)
{
componente++;
long f = 1, l = 1;
com[var] = componente;
cd[f] = nod;
while(f <= l)
{
for(long i = 1; i <= v[cd[f]]; i++)
{
if(com[c[cd[f]][i]] != componente)
{
com[c[cd[f]][i]] = componente;
l++;
cd[l] = c[cd[f]][i];
}
}
f++;
}
}
int main()
{
long a, b, m;
in>>n>>m;
for(var = 1; var <= m; var++)
{
in>>a>>b;
v[a]++;
v[b]++;
}
in.close();
for(var = 1; var <= n; var++)
c[var] = new long[v[var] + 1];
file>>n>>m;
for(var = 1; var <= m; var++)
{
file>>a>>b;
c[a][v1[a] + 1] = b;
v1[a]++;
c[b][v1[b] + 1] = a;
v1[b]++;
}
file.close();
for(var = 1; var <= n; var++)
if(v[var] == 0)
com[var]= ++componente;
else if(com[var] == 0)
dfs(var);
out<<componente<<"\n";
out.close();
return 0;
}