Cod sursa(job #1308997)

Utilizator deea101Andreea deea101 Data 5 ianuarie 2015 00:33:50
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.79 kb
#define NMAX 100001
#include <algorithm> 

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();
}