【BFS】BZOJ省选十连测 Cycle

分析：

蛤？
这题绝对有问题。。。
复杂度明显不对头。。。

它的想法其实就是找到一个点，判断它与它周围的点能否构成环，然后不能再删去这个点。。。

然而。。。他每次都memset了一发，这不T？服都服了。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1010
using namespace std;
typedef vector<int> vi;
vector<int> a[MAXN];
int mark[MAXN],done[MAXN];
bool lk[MAXN][MAXN],vis[MAXN];
int que[MAXN];
vi bfs(int s){
    int l=0,r=0;que[++r]=s;vis[s]=1;while(l!=r){
    int u=que[++l];for(int i=0;i<int(a[u].size());i++)if(done[a[u][i]]==0&&mark[a[u][i]]&&vis[a[u][i]]==0){
    vis[a[u][i]]=1;que[++r]=a[u][i];}}vi res;for(int i=1;i<=r;i++)res.push_back(que[i]);return res;
}	
int q[MAXN],pre[MAXN];
void find_cir(int x,int y,int key){
    memset(vis,0,sizeof vis);int l=0,r=0;q[++r]=x;vis[x]=1;pre[x]=0;while(l!=r){
    int u=q[++l];for(int i=0;i<int(a[u].size());i++){
    int v=a[u][i];if(v==y){
    pre[y]=u;for(int i=y;i;i=pre[i])PF("%d ",i);PF("%d",key);return ;}else if(done[v]==0&&vis[v]==0&&mark[v]){
    q[++r]=v;pre[v]=u;vis[v]=1;	}}}
}
bool solve(vi &les){
    if(les.size()<=3)return 0;int u=les[0];memset(vis,0,sizeof vis);memset(done,0,sizeof done);memset(mark,0,sizeof mark);vector<vi> les_part;for(int i=0;i<int(les.size());i++){
    mark[les[i]]=1;if(lk[les[i]][u])done[les[i]]=1;}done[u]=1;for(int k=0;k<int(les.size());k++)if(vis[les[k]]==0&&done[les[k]]==0){
    vi nles=bfs(les[k]),nc;for(int i=0;i<int(nles.size());i++){
    int u=nles[i];for(int j=0;j<int(a[u].size());j++)if(done[a[u][j]])nc.push_back(a[u][j]);}sort(nc.begin(),nc.end());nc.erase(unique(nc.begin(),nc.end()),nc.end());for(int i=0;i<int(nc.size());i++)if(mark[nc[i]]==1)for(int j=0;j<int(nc.size());j++)if(i!=j&&lk[nc[i]][nc[j]]==0){
    find_cir(nc[i],nc[j],u);return 1;}for(int i=0;i<int(nc.size());i++)nles.push_back(nc[i]);les_part.push_back(nles);}vi ad;for(int i=0;i<int(a[u].size());i++)if(mark[a[u][i]])ad.push_back(a[u][i]);for(int i=0;i<int(les_part.size());i++)if(solve(les_part[i]))return 1;return solve(ad);
}
int main(){
    freopen("cycle.in","r",stdin);
// freopen("cycle.out","w",stdout);int T;SF("%d",&T);while(T--){
    int n,m,u,v;vi les;memset(lk,0,sizeof lk);SF("%d%d",&n,&m);for(int i=1;i<=n;i++)a[i].clear();for(int i=1;i<=m;i++){
    SF("%d%d",&u,&v);	if(lk[u][v])continue;lk[u][v]=lk[v][u]=1;a[u].push_back(v);a[v].push_back(u);}for(int i=1;i<=n;i++)les.push_back(i);if(solve(les)==0)PF("no");PF("\n");}
}