Pagini recente » Cod sursa (job #3272482) | Cod sursa (job #1320001) | Cod sursa (job #2383202) | Cod sursa (job #2687873) | Cod sursa (job #3164959)
//LISTE DE ADIACENTA
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int NMAX=100000;
vector <int> G[NMAX+1];
queue <int> q;
bool vis[NMAX+1];
int d[NMAX+1];
int n, m;
void BFS(int x);
void DFS(int x);
int ComponenteCounter();
int main()
{
int z;
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
// G[y].push_back(x);
}
/* Commented out the print statements
for(int i = 1; i <= n; i++)
{
for(auto x:G[i])
{
cout << x << " ";
}
cout << endl;
}
*/
for (int i = 1; i <= n; i++)
d[i] = -1;
fout << ComponenteCounter();
/*for (int i = 1; i <= n; i++)
{
fout << d[i];
if (i != n)
fout << " ";
}*/
fin.close();
fout.close();
return 0;
}
void BFS(int x)
{
q.push(x);
d[x] = 0;
vis[x] = true;
while(!q.empty())
{
int y = q.front();
q.pop();
for(auto i : G[y])
{
if(!vis[i])
{
q.push(i);
vis[i] = true;
d[i] = d[y] + 1;
}
}
}
}
void DFS(int x)
{
vis[x] = true;
for(auto i : G[x])
{
if(!vis[i])
{
DFS(i);
}
}
}
int ComponenteCounter()
{
int componentsCount = 0;
for (int i = 1; i <= n; i++)
{
vis[i] = false;
}
for (int i = 1; i <= n; i++)
{
if(!vis[i])
{
DFS(i);
componentsCount++;
}
}
return componentsCount;
}