POJ1236 Network of schools

解决两个问题，对于给定的有向图，需要给多少个点可以遍历整个图，需要加多少条边可以使整个图变得强连通~

思路：用tarjan进行缩点，得到一个scc图，算出有n个入度为0的点，m个出度为0的点，第一个答案就是n,第二个答案就是max(n,m)

链式前向星版本：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=10014;
int N,M,x,y;
int low[maxn];
int dfn[maxn];
int cnt;
int scc;
int pos[maxn];
int in[maxn];
int out[maxn];
stack<int> st;

struct node {
    int u;
    int v;
    int w;
    int next;
}edge[maxn];
int head[maxn];
int tol;
void addedge (int u,int v) {
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol].next=head[u];
    head[u]=tol++;
} 


void tarjan (int x) {
    low[x]=dfn[x]=++cnt;
    st.push(x);
    for (int i=head[x];i!=-1;i=edge[i].next) {
        int v=edge[i].v;
        if (!low[v]) {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if (!pos[v]) 
            low[x]=min(low[x],dfn[v]);
    } 
    if (low[x]==dfn[x]) {
        scc++;
        while (1) {
            int u=st.top();
            st.pop();
            low[u]=low[x];
            pos[u]=scc;
            if (u==x) break;
        }
    }
}

void build () {
    for (int i=1;i<=N;i++) 
        for (int j=head[i];j!=-1;j=edge[j].next) 
            if (pos[i]!=pos[edge[j].v]) {
                out[pos[i]]++;
                in[pos[edge[j].v]]++;
            }
}


int main () {
    scanf("%d",&N);
    memset(head,-1,sizeof(head));
    for (int i=1;i<=N;i++) 
        while (scanf("%d",&x)&&x) 
            addedge(i,x);
    for (int i=1;i<=N;i++)
        if (!low[i]) tarjan(i);
    build();
    int rd=0;
    int cd=0;
    for (int i=1;i<=scc;i++) {
        if (in[i]==0) rd++;
        if (out[i]==0) cd++;
    }
    if (scc==1) printf("1
0
");
    else printf("%d
%d
",rd,max(rd,cd));
    return 0;
}

邻接表版本：

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn=1014;
vector<int> g[maxn];
int N,M,x,y;
int low[maxn];
int dfn[maxn];
int cnt;
int scc;
int pos[maxn];
int in[maxn];
int out[maxn];
stack<int> st;
void tarjan (int x) {
    low[x]=dfn[x]=++cnt;
    st.push(x);
    for (int i=0;i<g[x].size();i++) {
        if (!low[g[x][i]]) {
            tarjan(g[x][i]);
            low[x]=min(low[x],low[g[x][i]]);
        }
        else if (!pos[g[x][i]])low[x]=min(low[x],dfn[g[x][i]]);
    }
    if (low[x]==dfn[x]) {
        scc++;
        while (1) {
            int u=st.top();
            st.pop();
            low[u]=low[x];
            pos[u]=scc;
            if (u==x) break;
        }
    }
} 
void build () {
    for (int i=1;i<=N;i++) {
        for (int j=0;j<g[i].size();j++) {
            if (pos[i]!=pos[g[i][j]]) {
                out[pos[i]]++;
                in[pos[g[i][j]]]++;
            }
        }
    }
}
int main () {
    scanf ("%d",&N);
    for (int i=1;i<=N;i++) {
        while (scanf("%d",&x)&&x) g[i].push_back(x);
    }
    for (int i=1;i<=N;i++) 
    if (!low[i]) tarjan(i);
    build ();
    int rd=0;
    int cd=0;
    for (int i=1;i<=scc;i++) {
        if (in[i]==0) rd++;
        if (out[i]==0) cd++;
    }
    if (scc==1) printf ("1
0
");
    else printf ("%d
%d
",rd,max(rd,cd));
    return 0;
}