Pagini recente » Cod sursa (job #2716719) | Cod sursa (job #534273) | Cod sursa (job #3250425) | Cod sursa (job #2579132) | Cod sursa (job #1345598)
#include <cstdio>
#include <vector>
using namespace std;
class LinkedList
{
public:
int info;
LinkedList *next, *prev;
LinkedList()
{
next = NULL;
prev = NULL;
}
LinkedList(int info)
{
next = NULL;
prev = NULL;
this->info = info;
}
void addElement(int info)
{
LinkedList * aux = new LinkedList(info);
aux->next = next;
aux->prev = this;
next = aux;
}
void deleteNext()
{
if(next == NULL)
return;
next->next->prev = this;
next = next->next;
}
};
class Stack
{
public:
LinkedList top;
void push(int element)
{
if(top.next!=NULL)
{
top.next->prev = new LinkedList(element);
top.next->prev->next = top.next;
top.next->prev->prev = ⊤
top.next = top.next->prev;
return;
}
top.next = new LinkedList(element);
top.next->prev = ⊤
}
int pop()
{
int aux = top.next->info;
top.next = top.next->next;
if(top.next!=NULL)
top.next->prev = ⊤
return aux;
}
bool isEmpty()
{
return top.next == NULL;
}
int peek()
{
return top.next->info;
}
};
vector<int>edges[100002];
int visited[100002];
void visit (Stack s, int nr)
{
while(s.isEmpty()==false)
{
int current = s.pop();
for(int i=0; i<edges[current].size(); ++i)
if(visited[edges[current][i]]==0)
{
visited[edges[current][i]] = nr;
s.push(edges[current][i]);
}
}
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int n, m, i, j;
scanf("%d%d", &n, &m);
for(i=1; i<=m; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
edges[y].push_back(x);
edges[x].push_back(y);
}
j=1;
for(i=1; i<=n; ++i)
if(visited[i]==0)
{
Stack s;
s.push(i);
visited[i] = j;
visit(s, j);
++j;
}
printf("%d\n", j-1);
return 0;
}