Pagini recente » Cod sursa (job #574078) | Cod sursa (job #1719897) | Cod sursa (job #3170457) | Cod sursa (job #1305690) | Cod sursa (job #2785245)
#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
#define N 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
queue<int> q;
class Graph {
private:
int n, m;
vector<int> adlist[N];
bool viz[N] = {0};
int dist[N] = {0};
public:
void readDirected();
void readUndirected();
Graph(int n, int m):n(n), m(m){}
void bfs(int first);
void dfs(int first);
void printDist();
void connectedComponents();
};
void Graph::readDirected()
{
int i, x, y;
for(i = 1; i <= m; ++i)
{
fin >> x >> y;
adlist[x].push_back(y);
}
}
void Graph::readUndirected() {
int i, x, y;
for(i = 1; i <= m; ++i)
{
fin >> x >> y;
adlist[x].push_back(y);
adlist[y].push_back(x);
}
}
void Graph::bfs(int first){
int node, i, dim;
dist[first] = 1;
viz[first] = 1;
q.push(first);
while(!q.empty())
{
node = q.front();
q.pop();
dim = adlist[node].size();
for(i = 0; i < dim; ++i)
if(!viz[adlist[node][i]])
{
cout << adlist[node][i] <<" ";
viz[adlist[node][i]] = 1;
dist[adlist[node][i]] = dist[node] + 1;
q.push(adlist[node][i]);
}
}
}
void Graph::dfs(int node){
int i, dim;
viz[node] = 1;
dim = adlist[node].size();
for(i = 0; i < dim; ++i)
if(!viz[adlist[node][i]])
dfs(adlist[node][i]);
}
void Graph::printDist()
{
int i;
for(i = 1; i <= n; ++i)
fout << dist[i] - 1 << " ";
}
void Graph::connectedComponents() {
int i, nr = 0;
for(i = 1; i <= n; ++i)
if(!viz[i])
{
nr++;
dfs(i);
}
fout << nr;
}
int main()
{
int i, first, n, m;
fin >> n >> m;
Graph g(n, m);
/*
g.readOriented();
g.bfs(first);
g.printDist();
*/
g.readUndirected();
g.connectedComponents();
return 0;
}