有向图输出所有环，相同的环仅输出字典序最小的序列-蒲公英云

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

数据输入

该有向图用链式图存储

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

运行结果

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