Pagini recente » Cod sursa (job #44646) | Cod sursa (job #3240821) | Cod sursa (job #1452760) | Cod sursa (job #1286622) | Cod sursa (job #780401)
Cod sursa(job #780401)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define ALB 1
#define GRI 2
#define NEGRU 3
vector< vector<int> > graph;
vector<int> c, d, f, pi;
int timp;
void explorare(int node)
{
d[node] = timp++;
c[node] = GRI;
for(int i = 0; i < graph[node].size(); i++)
{
if(c[graph[node][i]] == ALB)
{
pi[graph[node][i]] = node;
explorare(graph[node][i]);
}
}
c[node] = NEGRU;
f[node] = timp++;
}
int dfs()
{
c.resize(graph.size());
d.resize(graph.size());
f.resize(graph.size());
pi.resize(graph.size());
for(int i = 1; i < graph.size(); i++)
{
c[i] = ALB;
pi[i] = 0;
}
timp = 0;
for(int i = 1; i < graph.size(); i++)
{
if(c[i] == ALB)
{
explorare(i);
}
}
return (int)count(pi.begin(), pi.end(), 0) - 1;
}
int main()
{
ifstream in ("dfs.in");
ofstream out ("dfs.out");
int n, m, x, y;
in >> n >> m;
graph.resize(n + 1);
for(int i = 0; i < m; i++)
{
in >> x >> y;
graph[x].push_back(y);
}
out << dfs();
out.close();
in.close();
return 0;
}