萌新球调tarjan /kel

MC小萌新 @ 2021-09-25 21:26:54

#include <iostream>
using namespace std;
int n,m,u,v,dfn[11000],stack[11000],low[11000],sze,start[11000],t,cnt,belong[11000];
bool ins[11000],vis[11000],vis1[11000];
struct edge{
    int e,next;
}ed[110000];
void add(int u,int v,int k){
    ed[k].next=start[u];
    start[u]=k;
    ed[k].e=v;
}
void dfs(int now){
    dfn[now]=low[now]=++t;
    vis1[now]=1;
    stack[++sze]=now;
    ins[now]=1;
    for(int i=start[now];i!=0;i=ed[i].next){
        int e=ed[i].e;
        vis1[e]=1;
        if(!dfn[e]){
            dfs(e);
            low[now]=min(dfn[now],low[e]);
        }
        else{
            if(ins[e]){
                low[now]=min(low[now],dfn[e]);
            }
        }
    }
    if(dfn[now]==low[now]){
        ++cnt;
        while(stack[sze]!=now){
            belong[stack[sze]]=cnt;
            ins[stack[sze--]]=0;
            vis1[stack[sze]]=1;
        }
        belong[stack[sze]]=cnt;
        vis1[stack[sze]]=1;
        ins[stack[sze--]]=0;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>u>>v;
        add(u,v,i);
    }
    dfs(1);
    for(int i=1;i<=n;++i)
        if(vis1[i]==0)
            ++cnt;
    cout<<cnt<<endl;
    for(int i=1;i<=n;++i){

        if(!vis[i]){
            vis[i]=1;
            cout<<i<<" ";
            for(int j=i+1;j<=n;++j){
                if(belong[j]==belong[i]){
                    cout<<j<<" ";
                    vis[j]=1;
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

by KonJAC_xrs @ 2021-09-25 21:47:45

不保证图联通，加上这个试试

for(register ll i=1;i<=n;i++)
    if(!dfn[i])
        tarjan(i);

还有数组别定义成stack，可能出锅，换一个。

by KonJAC_xrs @ 2021-09-25 21:51:47

不能只从1开始啊，不能只dfs（1）qwq；

你想，万一是两个孤立的“小岛”，那dfs1就只缩点了1所在的那个“岛”，其他的就没有缩点就错了，所以每个点都判断一下。

by MC小萌新 @ 2021-09-25 22:04:26

@xrs蒟蒻 改成这样了 还是WA

#include <iostream>
using namespace std;
int n,m,u,v,dfn[11000],sta[11000],low[11000],sze,start[11000],t,cnt,belong[11000];
bool ins[11000],vis[11000],vis1[11000];
struct edge{
    int e,next;
}ed[110000];
void add(int u,int v,int k){
    ed[k].next=start[u];
    start[u]=k;
    ed[k].e=v;
}
void dfs(int now){
    dfn[now]=low[now]=++t;
    vis1[now]=1;
    sta[++sze]=now;
    ins[now]=1;
    for(int i=start[now];i!=0;i=ed[i].next){
        int e=ed[i].e;
        vis1[e]=1;
        if(!dfn[e]){
            dfs(e);
            low[now]=min(dfn[now],low[e]);
        }
        else{
            if(ins[e]){
                low[now]=min(low[now],dfn[e]);
            }
        }
    }
    if(dfn[now]==low[now]){
        ++cnt;
        while(sta[sze]!=now){
            belong[sta[sze]]=cnt;
            ins[sta[sze--]]=0;
            vis1[sta[sze]]=1;
        }
        belong[sta[sze]]=cnt;
        vis1[sta[sze]]=1;
        ins[sta[sze--]]=0;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>u>>v;
        add(u,v,i);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            dfs(i);
//    for(int i=1;i<=n;++i)
//        if(vis1[i]==0)
//            ++cnt;
    cout<<cnt<<endl;
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            vis[i]=1;
            cout<<i<<" ";
            for(int j=i+1;j<=n;++j){
                if(belong[j]==belong[i]){
                    cout<<j<<" ";
                    vis[j]=1;
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

by MC小萌新 @ 2021-09-25 22:12:12

看评测好像cnt WA掉了就离谱

by KonJAC_xrs @ 2021-09-25 22:12:24

让我看一下qwq

by MC小萌新 @ 2021-09-25 22:15:25

谢谢啦qwq

by KonJAC_xrs @ 2021-09-25 22:28:40

就是3个问题啊

1.tarjan写挂了

 if(!dfn[e]){
            dfs(e);
            low[now]=min(dfn[now],low[e]);
        }

在第一个判断应该是

low[now]=min(low[now],low[e]);

2.数组开大点（不知道是不是因为这个qwq）

3.最后枚举的时候要这样

for(ll j=i+1;j<=n;++j)
                if(belong[j]==belong[i] and !vis[j])
                {
                    cout<<j<<" ";
                    vis[j]=1;
                }
            cout<<endl;

by MC小萌新 @ 2021-09-25 22:31:56

@xrs蒟蒻 谢谢大佬！过了qwq

by KonJAC_xrs @ 2021-09-25 22:32:31

我码风丑啊，不要嫌弃。

（话说您的tarjan好像写的有点麻烦？可以看我的qwq）

#warning By KonjAC_xrs
#warning ( testing == 1 ) ? Yes : No
#warning Only for testing

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while ( isdigit(ch)) {    x=x*10+ch-48; ch=getchar();}
    return x*f;
}

void write(ll x)
{
    if(x<0) putchar('-') , x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

//const ll inf=;
//const ll mod=;
const ll nore=2e5+20;

ll n,m,u,v,sze,t,cnt;
ll dfn[nore],sta[nore],low[nore],belong[nore];
bool ins[nore],vis[nore];

ll tot,ver[nore<<1],nxt[nore<<1],head[nore];
inline void add(ll x,ll y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}

void dfs(ll now)
{
    dfn[now]=low[now]=++t;
    sta[++sze]=now;
    ins[now]=1;
    for(ll i=head[now];i;i=nxt[i])
    {
        ll e=ver[i];
        if(!dfn[e])
        {
            dfs(e);
            low[now]=min(low[now],low[e]);
        }
        else if(ins[e])
            low[now]=min(low[now],dfn[e]);
    }
    if(dfn[now]==low[now])
    {
        ll z;
        cnt++;
        do{
            z=sta[sze--];
            belong[z]=cnt;
            ins[z]=false;
        }while(now!=z);
    }
}

int main()
{
    n=read(); m=read();
    for(ll i=1,u,v;i<=m;++i)
    {
        u=read(); v=read();
        add(u,v);
    }
    for(ll i=1;i<=n;++i)
        if(!dfn[i])
            dfs(i);
    cout<<cnt<<endl;
    for(ll i=1;i<=n;++i)
    {
        if(!vis[i])
        {
            vis[i]=1;
            cout<<i<<" ";
            for(ll j=i+1;j<=n;++j)
                if(belong[j]==belong[i] and !vis[j])
                    cout<<j<<" " , vis[j]=1;
            cout<<endl;
        }
    }
    return 0;
}