Pagini recente » Cod sursa (job #2824112) | Cod sursa (job #1311823) | Cod sursa (job #1988687) | Cod sursa (job #2985777) | Cod sursa (job #815400)
Cod sursa(job #815400)
#include <fstream>
#include <vector>
#define MAX_N 100001
class Node
{
public:
int color;
std::vector<int> neighbours;
};
Node Graf[MAX_N];
void dfs(int _node, int _color)
{
Graf[_node].color = _color;
for (int i = 0; i < Graf[_node].neighbours.size(); ++ i)
if (Graf[Graf[_node].neighbours[i]].color == 0)
dfs(i, _color);
}
int main()
{
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int N, M, x, y;
fin>>N>>M;
while(M--)
{
fin>>x>>y;
Graf[x].neighbours.push_back(y);
}
bool bFound = true;
int color = 0;
for (color = 1; bFound; ++ color)
{
bFound = false;
for (x = 1; x <= N; ++ x)
{
if (Graf[x].color == 0)
{
bFound = true;
break;
}
}
if (bFound)
dfs(x, color);
}
fout<<color;
return 0;
}