拓扑排序近似板子题

拓扑排序 需要是有相图且没有环即可使用

• 1. 建立连接表 计算每个点入度
  2. 把入度为0进入队列 然后bfs搜索 取除节点把他相邻的边砍掉 也就是指向的节点入度减一若减完入度为0进队
  3. 一直到bfs结束若答案中的数目和所有节点数目相同则无环可以有答案反之则有环 没有答案

#define pb push_back
#define ppb pop_back
#define p push
#define pp pop
#define Fo(i,n,m) for(int i=(n);i<(m);++i)
void solve()
{
	cin>>t;
    unordered_map<char,vector<char>>linjiebiao;
    unordered_map<char,int> rudu;
    unordered_set<char>dian;
	Fo(i,0,t)
    {
        string s;
        cin>>s;
        char X=s[0],Y=s[2],Z=s[3];
        linjiebiao[Y].pb(X);
        linjiebiao[X].pb(Z);
        rudu[X]++,rudu[Z]++;
        dian.insert(X),dian.insert(Y),dian.insert(Z);
    }
    for (char c:dian) 
    {
        if(rudu.find(c)==rudu.end()) 
            rudu[c]=0;
    }
    queue<char>dl;
    for(char c:dian) if(rudu[c]==0) dl.p(c);
    vec<char>ans;
    while(!dl.empty())
    {
        char dq=dl.front();
        ans.pb(dq);
        dl.pop();
        for(auto i:linjiebiao[dq])
        {
            rudu[i]--;
            if(rudu[i]==0)
            {
                dl.p(i);
            }    
        }
    }
    if(ans.size()==dian.size()) for(auto i:ans) cout<<i;
    else cout<<"No Answer";
	return;
}
int main()
{
    AC;
	solve();
    return 0;
}