终于a了!!!我勒个去。。。往往在无数次wa后重敲一遍就能ac。。。这句话很经典~
找了个ac程序对拍,结果发现那个ac程序错了,但是我交那个程序居然能ac!!我擦!!poj数据弱爆了啊!!尼玛还是专门用来卡哥的??
poj上一句很欠扁的话啊,虽然哥的程序是错的,但就是能ac!。。。艹!!彻底瞎了!!!!
然后又找了个ac程序对拍,自己生成的随即数据都tm有80mb了啊!!!可是答案都是一样的,令我很纠结。。。我又交了一遍,还是wa,无语凝噎,然后和小爽去吃饭,他说他有很多题都是这样。。。思路清楚的一逼,就是wa。。。- -!尼玛ac一题和会做一题还真是不一样的概念啊!!╮(╯▽╰)╭
晚上继续debug。。。快崩溃了,这种没测试数据的题目刷的真难受。。。
我感觉我的找错能力灰常强的,为什么就是wa啊!!!
无奈之下重敲了一遍。。。。。
后面发现居然是一个地方的now写成s.back()了,我擦!!!!tmd劳资直接撞死算了!!!!
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a) for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a) for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a) scanf(in64,&a)
#define SS(a) scanf("%d",&a)
#define LL(a) ((a)<<1)
#define RR(a) (((a)<<1)+1)
#define SZ(a) ((int)a.size())
#define PP(n,m,a) puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb push_back
#define CL(Q) while(!Q.empty())Q.pop()
#define MM(name,what) memset(name,what,sizeof(name))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-10;
const double pi = acos(-1.0);
const int maxn = 1011;
int n,m;
vector<int>g[maxn];
vector<int>lk[maxn];
vector<int>s;
queue<int>q;
bool hash[maxn][maxn];
int dfn[maxn];
int low[maxn];
bool ins[maxn];
int col[maxn];
bool you[maxn];
bool can[maxn];
int t[maxn];
int df,nf;
int x,y;
bool ok;
int ans;
void tarjan(int now)
{
int to,temp;
dfn[now]=low[now]=df++;
s.push_back(now);
FF(i,g[now].size())
{
to=g[now][i];
if(to == t[now])
{
continue;
}
if(!dfn[to])
{
t[to]=now;
tarjan(to);
low[now]=min(low[to],low[now]);
if(dfn[now] <= low[to])
{
do{
temp = s.back();
lk[nf].push_back(temp);
s.pop_back();
}while(temp != to);
lk[nf++].push_back(now);
}
}
else
{
low[now]=min(low[now],dfn[to]);
}
}
}
void start()
{
MM(dfn,0);
for(int i=1;i<=n;i++)
{
low[i]=inf;
}
MM(ins,false);
MM(hash,false);
MM(t,-1);
MM(col,0);
MM(can,false);
FF(i,maxn)
{
lk[i].clear();
}
s.clear();
df=nf=1;
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
nf--;
int now,to;
for(int i=1;i<=nf;i++)
{
if(lk[i].size()<2)
{
continue;
}
MM(you,false);
MM(col,0);
CL(q);
FF(j,lk[i].size())
{
now=lk[i][j];
you[now]=true;
}
q.push(lk[i][0]);
col[lk[i][0]]=1;
ok = false;
while(!q.empty())
{
now=q.front();
q.pop();
FF(u,g[now].size())
{
to=g[now][u];
if(!you[to])
{
continue;
}
if(!col[to])
{
col[to]=-col[now];
q.push(to);
}
else if(col[now]==col[to])
{
ok=true;
break;
}
}
if(ok)
{
break;
}
}
if(ok)
{
FF(u,lk[i].size())
{
now=lk[i][u];
can[now]=true;
}
}
}
ans=0;
FOR(i,1,n)
{
if(!can[i])
{
ans++;
}
}
cout<<ans<<endl;
return ;
}
int main()
{
while(cin>>n>>m)
{
if(!n && !m)
{
break;
}
MM(hash,false);
FF(i,maxn)
{
g[i].clear();
}
for(int i=1;i<=m;i++)
{
cin>>x>>y;
hash[x][y] = true;
hash[y][x] = true;
}
FOR(i,1,n) FOR(j,1,n)
{
if(i == j)
{
continue;
}
if(!hash[i][j])
{
g[i].push_back(j);
}
}
start();
}
return 0;
}
分享到:
相关推荐
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ 最接近点对问题 ACM北大 using namespace std; struct Point { float x; float y; };
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ2002-Squares 解题报告+AC代码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
poj 百练 题目分类 poj 百练 题目分类