Cod sursa(job #1321898)

Utilizator deea101Andreea deea101 Data 19 ianuarie 2015 17:29:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.17 kb
using namespace std;
#define NULL 0
#include <vector>
#include <cstring>

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