Pagini recente » Cod sursa (job #1706567) | Cod sursa (job #2296261) | Monitorul de evaluare | Cod sursa (job #2480514) | Cod sursa (job #2501745)
#include <cstdio>
#include <vector>
#include <queue>
#define maxVertices 101024
using namespace std;
int vertices,arces;
int visited[101024],sol;
vector <int> graph[maxVertices];
void addV(int from,int to) {
graph[from].push_back(to);
}
void read() {
int i,from,to;
scanf("%d%d",&vertices,&arces);
for(i=0;i<arces;++i) {
scanf("%d%d",&from,&to);
addV(from,to);
}
}
void mmset() {
int i;
for(i=1;i<=vertices;++i) {
visited[i]=-1;
}
}
void fillVertices(int startingVertice) {
queue <int> lastVisited;
int pos,i;
lastVisited.push(startingVertice);
visited[startingVertice]=0;
while(!lastVisited.empty()) {
pos=lastVisited.front();
lastVisited.pop();
for(auto&i:graph[pos]) {
if(visited[i]<0) {
visited[i]=visited[pos]+1;
lastVisited.push(i);
}
}
}
}
void solve() {
int i;
mmset();
for(i=1;i<=vertices;++i) {
if(visited[i]<0) {
++sol;
fillVertices(i);
}
}
}
void display() {
printf("%d",sol);
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
read();
solve();
display();
return 0;
}