这道题的暴力,不知道为什么,如果把75行的中间输出给注释掉答案就会爆掉,不删答案对的,为什么?
#include<iostream>
#include<queue>
using namespace std;
int n,m,b[1005],num,ans;
bool edge[1005][1005];
pair<int,int> p[1005];
int poww(int a)
{
int b=1;
for(int i=1;i<=a;i++)
{
b*=2;
b%=1000000007;
}
return b;
}
void find()
{
queue<int> q;
int M;
bool flag[1005];
for(int i=1;i<=m;i++)
{
edge[p[i].first][p[i].second]=0;
edge[p[i].second][p[i].first]=0;
for(int j=1;j<=n;j++)
{
if(b[j])
{
q.push(j);
flag[j]=1;
break;
}
}
while(!q.empty())
{
int t=q.front();
//cout<<t<<endl;
q.pop();
for(int j=1;j<=n;j++)
{
if(!flag[j]&&edge[t][j])
{
q.push(j);
flag[j]=1;
}
}
}
bool fg=0;
for(int j=1;j<=n;j++)
{
if(b[j]&&!flag[j])
{
fg=1;
break;
}
flag[j]=0;
}
if(!fg)M++;
fg=0;
edge[p[i].first][p[i].second]=1;
edge[p[i].second][p[i].first]=1;
//cout<<endl;
}
ans+=poww(M)%1000000007;
//cout<<ans<<endl;
}
void select()
{
for(int i=1;i<=num;i++)
{
for(int j=1;j<=n;j++)
{
b[j]=(i>>j-1)%2;
cout<<b[j];//这个注释掉答案就爆了
}
cout<<endl;
find();
}
}
int main()
{
cin>>n>>m;
int x,y,cnt=0;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
edge[x][y]=1;
edge[y][x]=1;
pair<int,int> pp;
pp.first=max(x,y);
pp.second=min(y,x);
p[++cnt]=pp;
}
num=(1<<n)-1;
select();
cout<<ans;
}