迷宫城堡

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 9893    Accepted Submission(s): 4433

3 3

1 2

2 3

3 1

3 3

1 2

2 3

3 2

0 0

Yes

No

有向图求SCC的裸题

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 10000 + 100

#define maxm 100000 + 1000

using namespace std;

int n, m;

struct node {

	int u, v, next;

};

node edge[maxm];

int head[maxn], cnt;

int low[maxn], dfn[maxn];

int dfs_clock;

int Stack[maxn];

bool Instack[maxn];

int top;

int Belong[maxn] , scc_clock;

void init(){

	cnt = 0;

	memset(head, -1, sizeof(head));

}

void addedge(int u, int v){

	edge[cnt] = {u, v, head[u]};

	head[u] = cnt++;

}

void getmap(){

    while(m--){

        int a, b;

        scanf("%d%d", &a, &b);

        addedge(a, b);

    }

}

void tarjan(int u, int per){

    int v;

    low[u] = dfn[u] = ++dfs_clock;

    Stack[top++] = u;

    Instack[u] = true;

    int have = 1;

    for(int i = head[u]; i != -1; i = edge[i].next){

        v = edge[i].v;

        if(v == per && have){

            have = 0;

            continue;

        }

        if(!dfn[v]){

            tarjan(v, u);

            low[u] = min(low[v], low[u]);

        }

        else if(Instack[v]){

            low[u] = min(low[u], dfn[v]);

        }

    }

    if(dfn[u] == low[u]){

        scc_clock++;

        do{

            v = Stack[--top];

            Instack[v] = false;

            Belong[v] = scc_clock;

        }while(u != v);

    }

}

void find(){

    memset(low, 0, sizeof(low));

    memset(dfn, 0, sizeof(dfn));

    memset(Instack, false, sizeof(Instack));

    memset(Belong, 0, sizeof(Belong));

    dfs_clock = scc_clock = top = 0;

    for(int i = 1; i <= n; ++i){

        if(!dfn[i])

            tarjan(i, i);

    }

}

void solve(){

    if(scc_clock == 1)

        printf("Yes\n");

    else

        printf("No\n");

}

int main (){

	while(scanf("%d%d", &n, &m), n || m){

        init();

        getmap();

        find();

        solve();

	}

	return 0;

}