#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=200010;
int h[N],ne[M],e[M],idx; //存储邻接表
int n,m;
int color[N]; //表示每个点所染的颜色

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool dfs(int u, int c)
{
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i]) //遍历与当前有关的所有根节点
    {
        int j = e[i];
        if (!color[j]) //若当前根节点没有染过色，就给他染色
        {
            if(!dfs(j,3-c)) return false;
        }
        else if( color[j] == c) return false; //如果当前的根节点与当前的点的颜色相同则矛盾
    }
    return true;
}
int main()
{
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--)
    {
        int a , b; 
        cin >> a >> b;
        add(a,b),add(b,a);    
    }
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    if (flag) puts("Yes");
    else puts("No");
    return 0;
}

并查集的简单运用

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010,INF=0x3f3f3f3f;
int p[N];
int n,m;
struct Edge
{
    int a,b,w;
    bool operator<(const Edge &W)const
    {
        return w<W.w;
    }
}edges[N];
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int kruskal() //根据权重排序所有边+并查集的简单运用
{
    sort(edges,edges+m);
    //初始化并查集
    for(int i=1;i<=n;i++) p[i]=i;

    int res=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;

        a=find(a),b=find(b);
        if(a!=b)
        {
            p[a]=b;
            res+=w;
            cnt++;
        }
    }
    if(cnt<n-1) return INF;
    else return res;
}
int main()
{
    cin >> n >>m;

    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin >>a >>b >>w;
        edges[i]={a,b,w};
    }

    int t=kruskal();

    if(t==INF) puts("impossible");
    else printf("%d\n",t);

    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int n,m;
bool st[N];
int dist[N];
int g[N][N];

int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];
        st[t]=true;

        for(int j=1;j<=n;j++)
        dist[j]=min(dist[j],g[t][j]); //更新点到集合的最小距离
    }
    return res;
}

int main()
{
    cin >>n >>m;
    memset(g,0x3f,sizeof g);

    while(m--)
    {
        int a,b,c;
        cin >>a >>b >>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
    if(t==INF) puts("impossible");
    else printf("%d\n",t);
    return 0;
}

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=10010,M=2010;
int ne[N],w[N],e[N],idx,cnt[N],dist[N],h[M];
bool st[N];
int n,m;
bool spfa()
{
    queue<int> q;

    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=true; //所有的元素都在队列中
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false; //表示该点不在队列中
        //与正常的spfa求差不多
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i]) //只有出现负权边的时侯才会进行更新否则输出全为0，这就是dist数组初始化为0的原因
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;

                if(cnt[j]>=n) return true;
                if(!st[j]) //首先它得是存在于负权欢中，它才能再次进入队列
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m;
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;
int h[N];
int e[N],ne[N],w[N],idx;
int n,m;
bool st[N];
int dist[N];
int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false; //表示出队
        for(int i=h[t];i!=-1;i=ne[i]) //用队头元素更新与其相关的边 
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i]) //松弛
            {
                dist[j]=dist[t]+w[i];
                if(!st[j]) //如果被更新后的点比之前更小了，则进入队列更新与之相关的点
                {
                 q.push(j);
                 st[j]=true; //表示进入队列
                }
            }
        }
    }
    return dist[n];
}
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m ;
    while(m--)
    {
        int a,b,c;
        cin >>a >>b >>c;
        add(a,b,c);
    }
    auto t=spfa();
    if(t==0x3f3f3f3f) puts("impossible");
    else printf("%d\n",t);
    return 0;
}

//解决有限边限制的最短路 —— bellman-ford 算法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int backup[N],dist[N]; //backup数组的存在意义在于防止串联的发生也就是一次只更新一代的最短路，不会出现隔代的情况
struct Edge {
    int a, b, c;
} edge[M]; //记录所有边，每次迭代只需要遍历所有边
void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++)
        {
            auto t=edge[j];
            dist[t.b]=min(dist[t.b],backup[t.a]+t.c);
        }
    }
}
int main()
{
    cin >> n >> m  >> k;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin >>a >> b >> c;
        edge[i]={a,b,c};
    }
    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

int main()
{
    int k;
    scanf("%d", &k);

    while (k -- )
    {
        LL n, d, e;
        scanf("%lld%lld%lld", &n, &d, &e);
        LL m = n - e * d + 2;
        LL dt = m * m - 4 * n;
        LL r = sqrt(dt);

        if (dt < 0 || r * r != dt) puts("NO");
        else printf("%lld %lld\n", (m - r) / 2, (m + r) / 2);
    }

    return 0;
}