Pagini recente » Cod sursa (job #2784191) | Cod sursa (job #2268027) | Cod sursa (job #2027621) | Cod sursa (job #1045327) | Cod sursa (job #1489611)
#include <fstream>
#include <vector>
using namespace std;
ifstream is ("dfs.in");
ofstream os ("dfs.out");
int N, M; //nodes, edges
int ConexComps;
vector <int> Graph[100001]; //graph
bool Visited[100001];
void Read();
void DFS(int Node);
int main()
{
Read();
for (int i = 1; i <= N; ++i)
if (Visited[i] == 0)
{
ConexComps++;
DFS(i);
}
os << ConexComps << '\n';
is.close();
os.close();
}
void Read() //graph input
{
is >> N >> M;
for (int x, y; M; --M)
{
is >> x >> y;
Graph[x].push_back(y);
Graph[y].push_back(x);
}
};
void DFS(int Node) //Depth First Search
{
Visited[Node] = 1;
for (const int& Next : Graph[Node])
if (Visited[Next] == 0)
DFS(Next);
};