Pagini recente » Cod sursa (job #1793401) | Cod sursa (job #770276) | Cod sursa (job #2926118) | Cod sursa (job #36324) | Cod sursa (job #1321897)
using namespace std;
#define NULL 0
#include <vector>
class stack
{
private:
struct node
{
int key;
node *next;
}*first;
public:
stack()
{
first=NULL;
}
void push(int x)
{
node *p;
p=new node;
p->key=x;
p->next=first;
first=p;
}
void pop()
{
node *p=first;
if(first!=NULL) first=first->next;
delete p;
}
int top()
{
if(first!=NULL)
return first->key;
}
bool empty()
{
return (first==NULL);
}
};
class Queue
{
private:
struct node
{
int key;
node *next;
}*first,*last;
public:
Queue()
{
first=last=NULL;
}
int front()
{
if(first!=NULL)
return first->key;
}
void push(int x)
{
node *p;
p=new node;
p->key=x;
p->next=NULL;
if(first==NULL)
first=last=p;
else
last->next=p;
last=p;
}
void pop()
{
node *p=first;
if(first!=NULL)
first=first->next;
delete p;
}
bool empty()
{
return (first==NULL);
}
};
#define NMAX 500001
class Graph
{
private:
vector <int> AdList[NMAX];
int comp[NMAX],totalComp,size;
public:
Graph()
{
memset(comp,0,sizeof(comp));
}
void setSize(int n)
{
size=n;
}
void addEdge(int i, int j)
{
AdList[i].push_back(j);
AdList[j].push_back(i);
}
void see(int node,int v[])
{
v[node]=totalComp;
}
bool unseen(int node, int v[])
{
if(!v[node]) return 1;
else return 0;
}
void dfs(int root)
{
stack s; int node;
s.push(root);
while(!s.empty())
{
node=s.top();
s.pop();
see(node,comp);
for(int i=0;i<AdList[node].size();i++)
if( unseen(AdList[node][i],comp) )
s.push(AdList[node][i]);
}
}
int Comp()
{
totalComp=0;
for(int i=1;i<=size;i++)
{
if( unseen(i,comp) )
{
totalComp++;
dfs(i);
}
}
return totalComp;
}
}G;
#include <fstream>
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<<G.Comp();
}