有向图输出所有环，相同的环仅输出字典序最小的序列

﹏ヽ暗。殇╰゛Y 2023-07-13 13:53 22阅读 0赞

### 注释超级详细。。不信你看不懂。。看不懂底下留言！！！！ ###

### 数据输入 ###

该有向图用链式图存储

a b;a c;b e;e b;c d;d a

![20200312172327381.png][]

### 运行结果 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70][]

#include<iostream>
    #include<string>
    #include<map>
    #include<vector>
    #include<algorithm>
    #include<set>
    using namespace std;
    
    //有向图中找出所有的环，重复的环只保留字典序最小的序列：比如abcda,bcdab是同一个环，只保留abcda 
    
    /*
    set<char>s;是用来记录哪些元素构成环 （set具有不重复性） 
    set<set<char> >set_circle_element;用来存储每个环的元素，
    当有一个新环被发现，就被加入到里面。同时这保证了相同环的最小字典序.
    比如发现有一个环是abcda，set_circle_element就记录了{a,b,c,d}。当发现bcdab这个环时，
    因为set_circle_element中已经有 {a,b,c,d}了，就不考虑bcdab这个环了。同理cdbac...
    
     vector<vector<char> >CIRCLE;用来存储存储字典序最小的环 
    */ 
    vector<char>expend;
    vector<char>circle;//记录每次的序列，是最小字典序的环就加入到 vector<vector<char> >CIRCLE中 
    vector<vector<char> >EXPAND;
    vector<vector<char> >CIRCLE;
    map<char,vector<char> >mp;//链式图 
    set<char>s;
    set<set<char> >set_circle_element;
    
    
    //
    /*
    比较函数 
    vector元素小的排前面
    要是两个vector一样大，就选字典序小的排前面 
    */ 
    int cmp(vector<char>a,vector<char>b)
    {
    	if(a.size()!=b.size())
    		return a.size()<b.size();
    	else
    	{
    		vector<char>::iterator it1,it2;
    		for(it1=a.begin(),it2=b.begin();it1!=a.end();it1++,it2++)
    			if((*it1)!=(*it2))
    				return (*it1)<(*it2);
    			else
    				continue;
    		return 1;
    	}
    } 
    
    //打印序列 
    void show()
    {
    	vector<char>::iterator it2;
    	for(it2=circle.begin();it2!=circle.end();it2++)
        {
        		cout<<(*it2)<<" ";
    	}
    	cout<<endl;
    }
    
    void dfs(char start)
    {
    	
    	//递归终点1 
    	 //s发现有重复元素说明出现了环，并且判断这个新字符是否和circle序列第一个元素相等 
    	if(s.find(start)!=s.end()&& start==*circle.begin())
    	{
    		circle.push_back(start);//circle加入新元素，此时circle是一个环 
    		
    		/*
    		//判断s在set_circle_element中是否出现过，
    		如果出现过，说明此时的circle不是最小字典序，就不用添加了，否则添加
    		*/ 
    		if(set_circle_element.find(s)==set_circle_element.end() ) 
    		{
    			set_circle_element.insert(s);//添加新的元素组合 
    			CIRCLE.push_back(circle);//添加一个新的字典序最小的环 
    		}
    		return ;
    	} 
    
    
    	//递归终点2 
    	/*
    	如果这个新的元素start在circle中出现过说明此时start在circle的中间且不是第一个（因为递归终点1已经判断过了），
    	要是再加入这个元素，会在circle序列中产生子环（abcdc），这是不允许的，所以return 
    	*/ 
    	vector<char>::iterator ret;
    	ret=find(circle.begin(), circle.end(), start); 
    	if(ret!=circle.end())
    		return;
    	
    	//递归终点3 :序列的长度都大于结点个数了，必须return 
    	if(circle.size()>mp.size())
    		return;
    	
    	//这个start不符合上面三个递归终点，将其加入circle序列和s集合 
    	s.insert(start);//s加入start 
    	circle.push_back(start);//circle加入start 
    	vector<char>::iterator it;
    	char next;
    	//用链式图（变量名为mp）索引为start的vector数组元素依次作为序列的下一个元素 
    	for(it=mp[start].begin();it!=mp[start].end();it++)
    	{
    		
    		next=(*it);
    		dfs(next);
    		
    	}
    	//这两条语句是为了恢复现场，恢复成没加入start的情形 
    	circle.pop_back();
    	s.erase(start);
    }
    
    int main()
    {
    	freopen("1.txt","r",stdin);
        char c1,c2;
        
        //构建链式图，此处因为每个人读入数据的格式不一样，需要自己修改 
        while(cin>>c1>>c2)
        {
            getchar();
            mp[c1].push_back(c2);
            //du[c2]++;
            s.insert(c2);
        }
        map<char,vector<char> >::iterator it;
    
        //输出链式图 
        cout<<"输出链式图"<<endl; 
        for(it=mp.begin();it!=mp.end();it++)
        {
        	char start=(*it).first;
        	
        	cout<<start<<":";
        	vector<char>::iterator it2;
        	for(it2=(*it).second.begin();it2!=(*it).second.end();it2++)
        	{
        		cout<<(*it2)<<" ";
    		}
    		cout<<endl;
    		
    	}
        
        
        /*
    	遍历链式图的每个结点，并用每个结点连接的元素作为 
    	*/ 
        s.clear();
        for(it=mp.begin();it!=mp.end();it++)//遍历链式图的每个结点 
        {
        	char start=(*it).first;//获取第一个结点 
        	
        	 vector<char>::iterator it2;
        	for(it2=(*it).second.begin();it2!=(*it).second.end();it2++)//并用每个结点连接的元素（vector）作为下一个元素 
        	{
        		//每次换新元素时都要重新把start加入，因为dfs之后会把s和circle清空 
    		    circle.push_back(start);
        	    s.insert(start);
      
        		dfs(*it2);//（*it2就是vector数组中的每个元素）开始递归。。。 
        		
        		//恢复现场，为下一个vector中的元素充当circle序列中start之后的元素做准备 
        		s.clear();
        		circle.clear();
    		}
    		//恢复现场，感觉这两句多余，但是为了保险，还是清除一下吧 
    		s.clear();
        	circle.clear();
    	}
        
        
        
        cout<<"打印所有环"<<endl; 
        sort(CIRCLE.begin(),CIRCLE.end(),cmp);//给 CIRCLE排序 
        
        //打印 CIRCLE，每个人的打印方式不一样，自己修改 
        vector<vector<char> >::iterator it1;
        vector<char>::iterator it2;
        for(it1=CIRCLE.begin();it1!=CIRCLE.end();it1++)
        {
        	for(it2=(*it1).begin();it2!=(*it1).end();it2++)
        	{
        		cout<<(*it2)<<" ";
    		}
    		cout<<";";
    	}
        
        return 0;
    }

[20200312172327381.png]: /images/20230529/151f691d501d430dba5f81a8d0164331.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20230529/e5b1b27fda6a4e01bb54af2542414eea.png