昨天算法课讲了强连通kosaraju算法,今天做课后题看到半连通问题,好久没做题了,就想写一写,证明自己的一些想法,结果悲剧了,各种无语的小错误......

题意其实就是判断图是否是半连通的,强连通缩点后:

1.拓扑排序判断每次队列中是否只有一个元素,看来的

#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
using namespace std;

int T,n,m;
bool vit[1001];
int ind[1001];
int mark[1001],scc;
deque<int> f;
vector<int> g[1001];
vector<int> gt[1001];
bool chong[1001][1001];
vector<int> *gs=gt;
void dfs(int s);
void dfsmain()
{
    memset(vit,false,sizeof(vit));
    f.clear();
    for(int i=1;i<=n;i++)
        if(!vit[i]) dfs(i);
}
void dfs(int s)
{
    vit[s]=1;
    for(unsigned i=0;i<g[s].size();i++)
        if(!vit[g[s][i]]) dfs(g[s][i]);
    f.push_front(s);
}
void tdfs(int s);
void tdfsmain()
{
    memset(mark,0,sizeof(mark));scc=0;
    memset(vit,0,sizeof(vit));
    while(!f.empty())
    {
        int u=f.front();f.pop_front();
        if(!vit[u])
            ++scc,tdfs(u);
    }
}
void tdfs(int s)
{
    vit[s]=1;mark[s]=scc;
    for(unsigned i=0;i<gt[s].size();i++)
        if(!vit[gt[s][i]]) tdfs(gt[s][i]);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int u,v;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            g[i].clear(),gt[i].clear();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            gt[v].push_back(u);
        }
        dfsmain();
        tdfsmain();
        //for(int i=1;i<=n;i++)
            //printf("%d ",mark[i]);
        //puts("");

        memset(ind,0,sizeof(ind));
        memset(chong,0,sizeof(chong));
        for(int i=1;i<=scc;i++)
            gs[i].clear();
        for(u=1;u<=n;u++)
            for(unsigned i=0;i<g[u].size();i++)
            {
                v=g[u][i];
                if(mark[u]!=mark[v] && !chong[mark[u]][mark[v]])
                    gs[mark[u]].push_back(mark[v]),
                        ind[mark[v]]++, chong[mark[u]][mark[v]]=1;
            }
        deque<int> q;
        for(int i=1;i<=scc;i++)
            if(!ind[i])
                q.push_back(i);
        bool failed=0;
        while(!q.empty())
        {
            if(q.size()!=1)
            {failed=1; break;}
            int u=q.front();q.pop_front();
            for(unsigned i=0;i<gs[u].size();i++)
            {
                int v=gs[u][i];
                if(--ind[v]==0)
                    q.push_back(v);
            }
        }
        if(failed)
            puts("No");
        else
            puts("Yes");
    }
}

2.或者直接dfs狂搜(不管是否已vit),得到dfs的最大深度,是否等于点数,看所有点是否能在一条路上,代码好写.

#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
using namespace std;

int T,n,m;
bool vit[1001];
int ind[1001];
int mark[1001],scc;
deque<int> f;
vector<int> g[1001];
vector<int> gt[1001];
bool chong[1001][1001];
vector<int> *gs=gt;
void dfs(int s);
void dfsmain()
{
    memset(vit,false,sizeof(vit));
    f.clear();
    for(int i=1;i<=n;i++)
        if(!vit[i]) dfs(i);
}
void dfs(int s)
{
    vit[s]=1;
    for(unsigned i=0;i<g[s].size();i++)
        if(!vit[g[s][i]]) dfs(g[s][i]);
    f.push_front(s);
}
void tdfs(int s);
void tdfsmain()
{
    memset(mark,0,sizeof(mark));scc=0;
    memset(vit,0,sizeof(vit));
    while(!f.empty())
    {
        int u=f.front();f.pop_front();
        if(!vit[u])
            ++scc,tdfs(u);
    }
}
void tdfs(int s)
{
    vit[s]=1;mark[s]=scc;
    for(unsigned i=0;i<gt[s].size();i++)
        if(!vit[gt[s][i]]) tdfs(gt[s][i]);
}
int maxl;
void finaldfs(int s,int l)
{
    if(l>maxl) maxl=l;
    for(unsigned i=0;i<gs[s].size();i++)
        finaldfs(gs[s][i],l+1);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int u,v;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            g[i].clear(),gt[i].clear();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            gt[v].push_back(u);
        }
        dfsmain();
        tdfsmain();
        //for(int i=1;i<=n;i++)
            //printf("%d ",mark[i]);
        //puts("");

        memset(ind,0,sizeof(ind));
        memset(chong,0,sizeof(chong));
        for(int i=1;i<=scc;i++)
            gs[i].clear();
        for(u=1;u<=n;u++)
            for(unsigned i=0;i<g[u].size();i++)
            {
                v=g[u][i];
                if(mark[u]!=mark[v] && !chong[mark[u]][mark[v]])
                    gs[mark[u]].push_back(mark[v]),
                        ind[mark[v]]++, chong[mark[u]][mark[v]]=1;
            }
        maxl=0;
        for(int i=1;i<=scc;i++)
            if(!ind[i])
                finaldfs(i,1);
        if(maxl==scc)
            puts("Yes");
        else
            puts("No");
    }
}