Pagini recente » Cod sursa (job #231527) | Cod sursa (job #2065468) | Cod sursa (job #1517747) | Cod sursa (job #2761069) | Cod sursa (job #1751857)
#include <fstream>
#include <queue>
using namespace std;
typedef struct adjNode
{
int identifier;
struct adjNode *next;
public:
adjNode(int id, struct adjNode* next) : identifier(id), next(next){}
}AdjNode;
AdjNode** ReadAdjencyLists(int n, int m, istream &fin);
void Dfs(int s, AdjNode** adjencyLists, bool* flagVector);
int main()
{
ifstream fin;
ofstream fout;
fout.open("dfs.out");
fin.open("dfs.in");
int n, m;
fin >> n >> m;
AdjNode** adjencyLists = ReadAdjencyLists(n, m, fin);
bool* flagVector = new bool[n + 1]();
int conexComp = 0;
for(int i = 1; i <= n; i++)
{
if(!flagVector[i])
{
conexComp++;
flagVector[i] = true;
Dfs(i, adjencyLists, flagVector);
}
}
fout << conexComp;
fin.close();
fout.close();
return 0;
}
AdjNode** ReadAdjencyLists(int n, int m, istream &fin)
{
AdjNode** adjencyLists = new AdjNode*[n + 1]();
int x, y;
for(int i = 1; i <= m; i++)
{
fin >> x >> y;
AdjNode* xToyArc = new AdjNode(y, adjencyLists[x]);
adjencyLists[x] = xToyArc;
AdjNode* yToxArc = new AdjNode(x, adjencyLists[y]);
adjencyLists[y] = yToxArc;
}
return adjencyLists;
}
void Dfs(int s, AdjNode** adjencyLists, bool* flagVector)
{
AdjNode* current = adjencyLists[s];
while(current)
{
if(!flagVector[current->identifier])
{
flagVector[current->identifier] = true;
Dfs(current->identifier, adjencyLists, flagVector);
}
current = current->next;
}
}