Pagini recente » Cod sursa (job #414881) | Cod sursa (job #2063415) | Cod sursa (job #2462682) | Cod sursa (job #2451607) | Cod sursa (job #2466722)
#include <fstream>
#include <vector>
using graph_t = std::vector<std::vector<int>>;
void dfs(int u, std::vector<bool> &seen, const graph_t &G)
{
seen[u] = true;
for (auto v : G[u])
if (!seen[v])
{
dfs(v, seen, G);
}
}
int solve(const graph_t &G)
{
std::vector<bool> seen(G.size(), false);
int c = 0;
for (int u = 0; u < G.size(); u++)
if (!seen[u])
{
c++;
dfs(u, seen, G);
}
return c;
}
graph_t read();
void write(int c);
int main()
{
auto G = read();
auto c = solve(G);
write(c);
return 0;
}
graph_t read()
{
std::ifstream fin("dfs.in");
int n, m, u, v;
fin >> n >> m;
graph_t G(n);
while (fin >> u >> v)
{
u--, v--;
G[u].push_back(v);
}
return G;
}
void write(int c)
{
std::ofstream fout("dfs.out");
fout << c << "\n";
}