Pagini recente » Cod sursa (job #1284106) | Cod sursa (job #2225858) | Cod sursa (job #1189972) | Cod sursa (job #1992732) | Cod sursa (job #715325)
Cod sursa(job #715325)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
long N[100001] = {0};
//vector<int> M[100000];
vector<int> *M;
int main(void)
{
fstream fin("dfs.in",ios::in);
fstream fout("dfs.out",ios::out);
long Noduri,Muchii,i,a,b,Co,k;
M = new vector<int>[100001];
pair<int,int> *c;
fin >> Noduri >> Muchii;
for (i = 0;i < Muchii;i += 1)
{
fin >> a >> b;
M[a].push_back(b);
}
Co = 0;
for (k = 1;k <= Noduri;k += 1)
{
if (N[k] <= 0)
{
Co += 1;
queue<pair<int,int> *> q;
q.push(new pair<int,int>(k,Co));
N[k] = Co;
while (q.empty() == 0)
{
c = q.front();
q.pop();
for (i = 0;i < M[c->first].size();i += 1)
{
if (N[M[c->first].at(i)] <= 0)
{
q.push(new pair<int,int>(M[c->first].at(i),Co));
N[M[c->first].at(i)] = Co;
}
}
}
}
}
fout << Co;
fin.close();
fout.close();
return 0;
}