who can give me some wa data??although I know my solution is wa.
Posted by
ben3ben 17 Apr 2012 15:06
#include <cstdio>
#include <string.h>
using namespace std;
struct dat_edge
{
int last,aim;
}edge[500000];
int temp[300],len_edge,pl[300],next[300],n,m;
void edge_insert(int x,int y)
{
len_edge++;
edge[len_edge].aim=y;
edge[len_edge].last=pl[x];
pl[x]=len_edge;
}
bool dfs(int root,int ps)
{
if (temp[root]==ps) return false;
if (ps==-1) return true;
temp[root]=ps;
int p=pl[root];
bool t;
while (p!=-1)
{
int tmp=edge[p].aim;
if (temp[tmp]==ps) { p=edge[p].last;continue; }
if (next[tmp]==-1) t=dfs(tmp,-1); else t=dfs(next[tmp],ps);
if (t)
{
next[root]=edge[p].aim;
next[edge[p].aim]=root;
return true;
}
p=edge[p].last;
}
return false;
}
int main()
{
//freopen("1099.in","r",stdin);
//freopen("1099.out","w",stdout);
int i,j,k,ans,coun,x,y;
bool ok;
scanf("%d",&n);
len_edge=-1;
for (i = 0;i<=n;i++) pl[i]=-1;
while (scanf("%d%d",&x,&y)!=EOF)
{
edge_insert(x,y);
edge_insert(y,x);
}
coun=0;
for (i = 0;i<=n;i++) next[i]=-1;
memset(temp,0,sizeof(temp));
ans=0;
for (i = 1;i<=n;i++)
{
ok=false;
if (next[i]==-1) ok=dfs(i,++coun);
if (ok) ans++;
}
printf("%d\n",ans*2);
for (i = 1;i<=n;i++)
if (next[i]>i)
{
printf("%d %d\n",i,next[i]);
}
}