cjb-poi2011garbage

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1000010
#define LF double
#define stack stck
struct EDGE { int adj,next; bool flag; }edge[2100000];
int gh[110000],tot=1;
void addedge(int x,int y){ edge[++tot].adj=y; edge[tot].next=gh[x]; edge[tot].flag=1; gh[x]=tot; }
int du[110000];
int n,m,instack[110000],stack[2100000],top;
vector<vector<int> > ans;
void dfs(int x)
{
    if (instack[x])
    {
        vector<int> f; f.clear();
        while (1)
        {
            int t=stack[top];
            instack[t]=0;
            f.pb(t);
            stack[top]=0;
            top--;
            if (t==x)break;
        }
        f.pb(f[0]);
        ans.pb(f);
    }
    for(int &p=gh[x];p;p=edge[p].next)
        if (edge[p].flag)
        {
            edge[p].flag=edge[p^1].flag=0;
            instack[x]=1;
            stack[++top]=x;
            dfs(edge[p].adj);
        }
}
int main()
{
    cin>>n>>m;
    rep(i,m)
    {
        int x,y,s,t;
        scanf("%d%d%d%d",&x,&y,&s,&t);
        if (s==t)continue;
        du[x]++; du[y]++;
        addedge(x,y);
        addedge(y,x);
    }
    rep(i,n)if (du[i]%2){ puts("NIE"); return 0; }
    rep(i,n)dfs(i);
    cout<<ans.size()<<endl;
    for(auto p:ans)
    {
        printf("%d",(int)p.size()-1);
        for(auto q:p)printf(" %d",q);
        puts("");
    }
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1000010
#define LF double
#define stack stck
struct EDGE { int adj,next; bool flag; }edge[2100000];
int gh[110000],tot=1;
void addedge(int x,int y){ edge[++tot].adj=y; edge[tot].next=gh[x]; edge[tot].flag=1; gh[x]=tot; }
int du[110000];
int n,m,instack[110000],stack[2100000],top;
vector<vector<int> > ans;
void dfs(int x)
{
    if (instack[x])
    {
        vector<int> f; f.clear();
        while (1)
        {
            int t=stack[top];
            instack[t]=0;
            f.pb(t);
            stack[top]=0;
            top--;
            if (t==x)break;
        }
        f.pb(f[0]);
        ans.pb(f);
    }
    for(int &p=gh[x];p;p=edge[p].next)
        if (edge[p].flag)
        {
            edge[p].flag=edge[p^1].flag=0;
            instack[x]=1;
            stack[++top]=x;
            dfs(edge[p].adj);
        }
}
int main()
{
    cin>>n>>m;
    rep(i,m)
    {
        int x,y,s,t;
        scanf("%d%d%d%d",&x,&y,&s,&t);
        if (s==t)continue;
        du[x]++; du[y]++;
        addedge(x,y);
        addedge(y,x);
    }
    rep(i,n)if (du[i]%2){ puts("NIE"); return 0; }
    rep(i,n)dfs(i);
    cout<<ans.size()<<endl;
    for(auto p:ans)
    {
        printf("%d",(int)p.size()-1);
        for(auto q:p)printf(" %d",q);
        puts("");
    }
    return 0;
}