Pagini recente » Cod sursa (job #2423591) | Cod sursa (job #1452155) | Cod sursa (job #2198939) | Cod sursa (job #1793112) | Cod sursa (job #2455575)
#include <fstream>
#include <vector>
#define nmax 100010
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int>A[nmax];
int Cost[nmax],G[nmax], S[nmax], nod1,nod2, ccon, n, m;
int i, j;
void dfs(int nod);
int main()
{
fin >> n >> m;
for (i = 1; i <= m; i++)
{
fin >> nod1 >> nod2;
A[nod1].push_back(nod2);
A[nod2].push_back(nod1);
G[nod1]++;
G[nod2]++;
}
for (i = 1; i <= n; i++)
{
if (Cost[i] == 0)
{
ccon++;
Cost[i] = ccon;
dfs(i);
}
}
fout << ccon;
return 0;
}
void dfs(int nod)
{
int L,i1;
L = 1;
S[L] = nod;
for(i1=1;i1<=L;i1++)
{
for (j = 0; j < G[S[i1]]; j++)
{
if (Cost[A[S[i1]][j]] == 0)
{
S[++L] = A[S[i1]][j];
Cost[S[L]] = Cost[S[i1]];
}
}
}
}