Pagini recente » Cod sursa (job #2031604) | Cod sursa (job #3250905) | Cod sursa (job #1668010) | Cod sursa (job #2504762) | Cod sursa (job #2782403)
#include<bits/stdc++.h>
using namespace std;
const int inf=(1e9);
const int dim=(1e5);
char buff[dim+5];
int pos=0;
void read(int &nr)
{
int semn=1;
nr=0;
while(!isdigit(buff[pos]))
{
if(buff[pos]=='-') semn=-1;
pos++;
if(pos==dim)
{
pos=0;
fread(buff,1,dim,stdin);
}
}
while(isdigit(buff[pos]))
{
nr=nr*10+buff[pos]-'0';
pos++;
if(pos==dim)
{
pos=0;
fread(buff,1,dim,stdin);
}
}
nr*=semn;
}
class Graph
{
private:
int m_nodes;
vector< vector< pair<int,int> > > m_adjList;
vector<pair<int, pair<int,int> > > m_edges;
vector<bool> m_visited;
bool m_areLabeled;
public:
Graph(int nodes,bool areLabeled)
{
m_nodes=nodes;
m_areLabeled=areLabeled;
m_adjList.resize(nodes+5);
}
void addEdge(int from, int to, int cost)
{
m_adjList[from].push_back(make_pair(to,cost));
m_edges.push_back(make_pair(from,make_pair(to,cost)));
}
void resetVisited()
{
m_visited.resize(m_nodes+5);
for(int i=0;i<=m_nodes;i++)
m_visited[i]=0;
}
vector<int> bfs(int source)
{
deque<int> q;
vector<int> distances(m_nodes+5,-1);
distances[source]=0;
q.push_back(source);
while(!q.empty())
{
int current = q.front();
q.pop_front();
for(auto it: m_adjList[current])
{
if(distances[it.first]==-1)
{
distances[it.first]=1+distances[current];
q.push_back(it.first);
}
}
}
return distances;
}
void dfs(int node)
{
m_visited[node]=1;
for(auto it:m_adjList[node])
{
if(m_visited[it.first]) continue;
dfs(it.first);
}
}
int getCC()
{
resetVisited();
int ans=0;
for(int i=1;i<=m_nodes;i++)
if(!m_visited[i]) dfs(i),ans++;
return ans;
}
};
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int n,m,x,y,source;
fread(buff,1,dim,stdin);
read(n);
read(m);
/** read(source);
//scanf("%d%d%d",&n,&m,&source);
Graph G(n,0);
for(int i=0;i<m;i++)
{
//scanf("%d%d",&x,&y);
read(x);
read(y);
G.addEdge(x,y,0);
}
vector<int> solution=G.bfs(source);
for(int i=1;i<=n;i++)
printf("%d ",solution[i]);**/
Graph G(n,0);
for(int i=1;i<=m;i++)
{
read(x);
read(y);
G.addEdge(x,y,0);
}
printf("%d\n",G.getCC());
return 0;
}