题解

34 条题解

  • 3
    @ 2018-08-14 21:22:40
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=100004,maxm=100004;
    int n,m=0,dfn[maxn],low[maxn],head[maxn],vis[maxn],cnt=0,deep=0,col[maxn],sum=0,num[maxn],out[maxn],ans=0,in[maxn];
    stack<int>s;
    struct node{
        int to,next;
    }e[maxm];
    void add(int u,int v){
        e[++cnt].to=v;
        e[cnt].next=head[u];
        head[u]=cnt;
    }
    void tarjan(int u){
        vis[u]=1;
        dfn[u]=low[u]=++deep;
        s.push(u);
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(vis[v]) low[u]=min(low[u],dfn[v]);
        }   
        if(dfn[u]==low[u]){
            col[u]=++sum;
            vis[u]=0;
            while(1){
                int x=s.top();
                s.pop();
                col[x]=sum;
                num[col[x]]++;
                vis[x]=0;
                if(u==x) break;
            }
        }
    }
    void shrink_point(){
        for(int i=1;i<=n;i++)
            for(int j=head[i];j;j=e[j].next){
                int v=e[j].to;
                if(col[i]!=col[v]) {out[col[v]]++;in[col[i]]++;}
            }
    }
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            int j;
            while(cin>>j){
                if(j==0) break;
                m++;add(i,j);
            }
        }
        for(int i=1;i<=n;i++)
         if(!dfn[i]) tarjan(i);
        shrink_point();
        int ans1=0;
        for(int i=1;i<=sum;i++){
         if(!out[i]) ans++;
         if(!in[i]) ans1++;
        }
        if(sum==1) cout<<"1"<<endl<<"0";
        else cout<<ans<<endl<<max(ans,ans1);
    }
    
    • @ 2018-09-04 09:32:24

      tarjan
      好评

  • 2
    @ 2018-09-04 14:48:41

    邻接矩阵
    tarjan算法
    题解:使用tarjan求强连通分量,求出的强连通分量可以看成一个点(叫做缩点),缩点后的图中入度为0的点的个数为a,出度为0的点的个数为b。
    第一问的答案就是a,第二问的答案就是max(a,b);

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    #define M 150
    using namespace std;
    int n,m,deep[M],low[M],v[M],tot,ans,inz[M],ans1,ans2,z[100100],belong[M],a[M][M],in[M],out[M],top;
    void tarjan(int x)
    {
        z[++top]=x;
        v[x]=1;
        inz[x]=1;
        deep[x]=++tot;
        low[x]=++tot;
        for(int i=1;i<=n;i++)
        {
            if(a[x][i]==1)
            {
                if(v[i]==0)
                {
                    tarjan(i);
                    low[x]=min(low[x],low[i]);
                }
                else
                {
                    if(inz[i]==1)
                    {
                        low[x]=min(low[x],deep[i]);
                    }
                }
            }
        }
        if(deep[x]==low[x])
        {
            ans++;
            int t;
            do
            {
                t=z[top--];
                inz[t]=0;
                belong[t]=ans;
            }while(t!=x);
        }
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int to;
            while(scanf("%d",&to)&&to)
            {
                a[i][to]=1;
            }
        }
        for(int i=0;i<=n;i++)
        {
            a[i][i]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(deep[i]==0)
            {
                tarjan(i);
            }
        }
        if(ans==1)
        {
            printf("1\n0");
            return 0;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]&&i!=j)
                {
                    if(belong[i]!=belong[j])
                    {
                        out[belong[i]]++;
                        in[belong[j]]++;
                    }
                }
            }
        }
        for(int i=1;i<=ans;i++)
        {
            if(in[i]==0)ans1++;
            if(out[i]==0)ans2++;    
        }
        ans2=max(ans1,ans2);
        printf("%d\n%d",ans1,ans2);
        return 0;
    }
    
  • 1
    @ 2017-10-02 20:16:22

    Kosaraju 比 Tarjan 好写多了 (挑战写法)

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 110;
    int n, res1, res2, cmp[maxn], in[maxn], out[maxn];
    bool vis[maxn];
    vector<int> G[maxn], rG[maxn], vs;
    
    void add_edge(int u, int v) {
        G[u].push_back(v);
        rG[v].push_back(u);
    }
    
    void dfs(int u) {
        vis[u] = true;
        for (int v : G[u]) {
            if (!vis[v]) {
                dfs(v);
            }
        }
        vs.push_back(u);
    }
    
    void rdfs(int u, int k) {
        vis[u] = true;
        cmp[u] = k;
        for (int v : rG[u]) {
            if (!vis[v]) {
                rdfs(v, k);
            }
        }
    }
    
    int scc() {
        memset(vis, false, sizeof(vis));
        vs.clear();
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                dfs(i);
            }
        }
        memset(vis, false, sizeof(vis));
        int k = 0;
        for (int i = vs.size() - 1; i >= 0; i--) {
            if (!vis[vs[i]]) {
                rdfs(vs[i], ++k);
            }
        }
        return k;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin >> n;
        for (int u = 1, v; u <= n; u++) {
            while (cin >> v && v != 0) {
                add_edge(u, v);
            }
        }
        int k = scc();
        for (int u = 1; u <= n; u++) {
            for (int v : G[u]) {
                if (cmp[u] != cmp[v]) {
                    out[cmp[u]]++;
                    in[cmp[v]]++;
                }
            }
        }
        for (int i = 1; i <= k; i++) {
            if (!out[i]) {
                res1++;
            }
            if (!in[i]) {
                res2++;
            }
        }
        if (k == 1) {
            cout << 1 << endl << 0 << endl;
            return 0;
        }
        cout << res2 << endl << max(res1, res2) << endl;
        return 0;
    }
    
  • 0
    @ 2017-10-18 13:52:37

    #6点错了的,可能是没有特判“只有一个强联通分量”的情况

  • 0
    @ 2009-07-28 20:58:14

    此题很沙茶。

    通过率巨高……

  • 0
    @ 2009-07-28 18:57:08

    USACO 5.3 schlnet

  • 0
    @ 2009-07-28 18:39:33

    没打算做。IOI。。囧rz..

  • 0
    @ 2009-07-28 19:44:00

    沙茶题……

    题解地址:http://xujieqi.blog.hexun.com/35535204_d.html

  • 0
    @ 2009-07-28 18:02:46

    感谢上天给我这样的一个机会:

    我第八个!

  • 0
    @ 2009-07-28 17:49:56

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    First Blood!!!

    终于拿了一血...把I打成0害我多交了1次...

    Kosaraju算法收缩强连通分量...

  • 0
    @ 2009-07-28 17:38:45

    地幔。。。

  • 0
    @ 2009-07-28 17:37:33

    第5个

  • 0
    @ 2009-07-28 17:33:16

    第三

  • 0
    @ 2009-07-28 17:29:26

    第二

  • -1
    @ 2016-07-09 15:59:42

    Network of Schools
    cpp
    #include <iostream>
    #include <stack>
    #include <vector>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    using namespace std;
    /*优化读入
    *@ param l 要读入的int
    */
    char ch_buffer;
    bool signum;
    inline void readInt(int&l) {
    l=0;
    do ch_buffer=getchar();
    while((ch_buffer<'0'||ch_buffer>'9')&&ch_buffer!='0'&&ch_buffer!='-');
    if(ch_buffer=='-')ch_buffer=getchar(),signum=true;
    while(ch_buffer<='9'&&ch_buffer>='0')l=(l<<3)+(l<<1)+ch_buffer-'0',ch_buffer=getchar();
    if(signum)l=-l,signum=false;
    }
    #define M 110/*题目中可能的最大点数*/
    stack<int> st;/*tarjan算法中的栈*/
    int DFN[M];/*深度优先搜索访问次序*/
    int Low[M];/*能追溯到的最早的次序*/
    int ComponentNumber=0;/*有向图强连通分量个数*/
    int Index=0;/*索引号*/
    vector<int> Edge[M];/*邻接表表示*/
    vector<int> Component[M];/*获得强连通分量结果*/
    int InComponent[M];/*记录每个点在第几号强连通分量里*/
    int ComponentDegree[M];/*记录每个强连通分量的度*/
    int inDegree[M];/*入度*/
    int outDegree[M];/*出度*/
    /*所给点的数量*/
    int n;
    /*无向图插入
    *@ param u 第一个顶点编号
    *@ param v 第二个顶点编号
    */
    inline void insertMulty(int u,int v) {
    Edge[u].push_back(v),Edge[v].push_back(u);
    }
    /*有向图插入
    *@ param u 顶点编号
    *@ param v 连通顶点的编号
    */
    inline void insert(int u,int v) {
    Edge[u].push_back(v);
    }
    /*初始化
    *@ param num_of_n 顶点的数量
    */
    inline void init(int num_of_n) {
    memset(DFN,0,sizeof(DFN));
    memset(Low,0,sizeof(Low));
    memset(inDegree,0,sizeof(inDegree));
    memset(outDegree,0,sizeof(outDegree));
    while(!st.empty()) st.pop();
    ComponentNumber=Index=0;
    n=num_of_n;
    }
    /*tajan+缩点*/
    void tarjan(int u) {
    DFN[u]=Low[u]=++Index;
    /*入栈*/
    st.push(u);
    int v;
    /*for each (u, v) in E*/
    for (int e=0; e<Edge[u].size(); e++) {
    v=Edge[u][e];
    if (!DFN[v]) {
    tarjan(v);
    Low[u]=min(Low[u],Low[v]);
    /*!InComponent[v]=>如果不在栈中,*/
    /*这里用这种写法,既可以缩点还能节约一个boolean数组*/
    } else if (!InComponent[v]) Low[u]=min(Low[u],Low[v]);
    }
    if (DFN[u]==Low[u]) {
    ComponentNumber++;
    do {
    v=st.top(),st.pop();
    /*记录强连通分量*/
    Component[ComponentNumber].push_back(v);
    /*缩点=>degree*/
    InComponent[v]=ComponentNumber;
    } while (v!=u);/*until v==u*/
    }
    }
    /*缩点*/
    inline void degree() {
    /*遍历*/
    for(int i=0; i<n; i++) {
    for(int j=0; j<Edge[i].size(); j++) {
    int k = Edge[i][j];
    /*这里的InComponent指的是点对应的强连通分量的编号*/
    /*等价于网上许多教程中的belong数组*/
    if(InComponent[i] != InComponent[k]) {
    /*统计入度*/
    inDegree[InComponent[k]]++;
    /*统计出度*/
    outDegree[InComponent[i]]++;
    }
    }
    }
    }
    int x;
    int main(int argc, char const *argv[]) {
    /* code */
    //freopen("in.in","r",stdin);
    readInt(n);
    init(n);
    for(int i=0; i<n; i++) {
    /*在c++中,while只根据最后一个","后的变量来判定条件是否成立*/
    while(readInt(x),x)
    /*所有编号都-1,节约空间*/
    /*如编号为1,存入为0*/
    x--, insert(i,x);
    }
    /*上面编号已减1,故从0开始遍历*/
    for(int i=0; i<n; i++)
    if(!DFN[i]) tarjan(i);
    /*特殊情况节约时间,避免再往下运行*/
    if(ComponentNumber==1)cout<<"1\n0\n",exit(0);
    /*缩点*/
    degree();
    /*统计入度为0的点*/
    int in_tot=0,out_tot=0;
    for(int i=1; i<=ComponentNumber; i++) {
    if(!inDegree[i]) in_tot++;
    if(!outDegree[i]) out_tot++;
    }
    cout<<in_tot<<"\n"<<max(in_tot,out_tot);
    return 0;
    }

  • -1
    @ 2015-07-20 22:12:41

    额,感觉和一道例题一样···
    #include <cstdlib>
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <cstring>
    using namespace std;

    const int maxn=10000;
    int pre[maxn],lowlink[maxn],sccno[maxn],dfsclock,scccnt;
    vector<int>G[maxn];
    stack<int>S;
    int n;
    void dfs(int u){
    pre[u]=lowlink[u]=++dfsclock;
    S.push(u);
    for(int i=0;i<G[u].size();i++){
    int v=G[u][i];
    if(!pre[v])
    {
    dfs(v);
    lowlink[u]=min(lowlink[u],lowlink[v]);

    }else if(!sccno[v])lowlink[u]=min(lowlink[u],pre[v]);

    }
    if(lowlink[u]==pre[u]){
    scccnt++;
    for(;;){
    int x=S.top();
    S.pop();
    sccno[x]=scccnt;
    if(x==u)break;

    }
    }
    }
    void find(int n){
    dfsclock=scccnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;i++)
    {
    if(!pre[i])dfs(i);
    }

    }
    int main()
    {
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
    int a;
    while(cin>>a&&a!=0)
    {
    G[i].push_back(a-1);
    }

    }
    find(n);

    //cout<<scccnt<<endl;
    int in0[maxn],out0[maxn];
    for(int i=1;i<=scccnt;i++)in0[i]=out0[i]=1;
    for(int u=0;u<n;u++)
    for(int u=0;u<n;u++)
    for(int i=0;i<G[u].size();i++)
    {
    int v=G[u][i];
    if(sccno[u]!=sccno[v])in0[sccno[v]]=out0[sccno[u]]=0;

    }
    int a=0,b=0;
    int ans1,ans2;
    for(int i=1;i<=scccnt;i++)
    {
    if(in0[i])a++;
    if(out0[i])b++;

    }
    ans2=max(a,b);
    if(scccnt==1){a=1,ans2=0;}
    cout<<a<<endl;
    cout<<ans2<<endl;
    system("PAUSE");
    return 0;
    }

  • -1
    @ 2013-10-29 20:07:19

    var
    a : array[1..100,0..100] of longint;
    n,i,j,ti,top,cnt,ans1,ans2,k : longint;
    sta,dfn,scc,low,inp,outp : array[0..107] of longint;

    function min(a,b : longint) : longint;
    begin
    if a<b then exit(a) else exit(b);
    end;

    procedure dfs(k : longint);
    var i,v,x : longint;
    begin
    inc(ti); dfn[k] := ti; low[k] := ti;
    inc(top); sta[top] := k;
    for i := 1 to a[k,0] do begin
    v := a[k,i];
    if dfn[v]=0 then begin
    dfs(v);
    low[k] := min(low[k],low[v]);
    end else
    if scc[v]=0 then low[k] := min(low[k],dfn[v]);
    end;
    if low[k]=dfn[k] then begin
    inc(cnt);
    repeat
    x := sta[top]; dec(top);
    scc[x] := cnt;
    if x=k then break;
    until false;
    end;
    end;

    begin
    readln(n);
    for i := 1 to n do begin
    read(j);
    while j<>0 do begin inc(a[i,0]); a[i,a[i,0]] := j; read(j); end;
    readln;
    end;
    for i := 1 to n do
    if dfn[i]=0 then dfs(i);
    for i := 1 to n do
    for j := 1 to a[i,0] do begin
    k := a[i,j];
    if scc[k]<>scc[i] then begin
    inc(inp[scc[k]]); inc(outp[scc[i]]);
    end;
    end;
    for i := 1 to cnt do
    if inp[i]=0 then inc(ans1) else
    if outp[i]=0 then inc(ans2);
    if ans1>ans2 then ans2 := ans1;
    if cnt=1 then ans2 := 0;
    writeln(ans1); writeln(ans2);
    end.

  • -1
    @ 2013-10-29 20:06:51

    强连通分量果然比双连通好打多了嗯哼~

  • -1
    @ 2013-10-18 12:02:42

    如果只有一个强连通分量,那么任务a=1,任务b=0;

信息

ID
1595
难度
5
分类
图结构 | 强连通分量贪心 点击显示
标签
递交数
1031
已通过
331
通过率
32%
被复制
1
上传者