Pagini recente » Clasament arhiva | Cod sursa (job #2650962) | Cod sursa (job #2761904) | Cod sursa (job #2761903) | Cod sursa (job #1308998)
#define NMAX 100001
#include <cstring>
struct node
{
int key;
node *next;
node()
{
next=NULL;
}
};
class List
{
private:
node *first,*last;
public:
List()
{
first=last=NULL;
}
node *front()
{
return first;
}
void push_back(int key)
{
node *p;
p=new node;
p->key=key;
if(last!=NULL) last->next=p;
else first=p;
last=p;
}
};
class stack
{
private:
node *first;
public:
stack()
{
first=NULL;
}
int top()
{
return first->key;
}
bool empty()
{
if(first==NULL) return 1;
else return 0;
}
void pop()
{
node *p=first;
first=first->next;
delete p;
}
void push(int x)
{
node *p;
p->key=x;
p->next=first;
first=p;
}
};
class Graph
{
private:
int N,components,comp[NMAX];
List v[NMAX];
bool visited[NMAX];
void visit(int node)
{
comp[node]=components;
}
public:
Graph()
{
memset(v,NULL,sizeof(v));
memset(comp,0,sizeof(comp));
memset(visited,0,sizeof(visited));
}
void setSize(int n)
{
N=n;
}
void addEdge(int i, int j)
{
v[i].push_back(j);
}
void DFS(int Node)
{
node *p;
p=v[Node].front();
visit(Node);
visited[Node]=1;
while(p!=NULL)
{
if(!visited[p->key])
DFS(p->key);
p=p->next;
}
}
void DFSiterative(int Node)
{
memset(visited,0,sizeof(visited));
stack s;
s.push(Node);
int x;
node *p;
while( !s.empty() )
{
x=s.top();
s.pop();
visit(x);
visited[x]=1;
p=v[x].front();
while(p!=NULL)
{
if(!visited[p->key])
s.push(p->key);
p=p->next;
}
}
}
int getComponents()
{
components=0;
for(int i=1;i<=N;i++)
{
if(!visited[i])
{
components++;
DFS(i);
}
}
return components;
}
}G;
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int main()
{
int N,M;
f>>N>>M;
G.setSize(N);
int x,y;
while(M--)
{
f>>x>>y;
G.addEdge(x,y);
G.addEdge(y,x);
}
g<<G.getComponents();
}