प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

[प्रश्नस्य स्रोतः] ।
https://www.acwing.com/समस्या/सामग्री/3590/

[शीर्षकविवरणम्] २.
अनिर्देशितं आलेखं तस्मिन् सर्वे किनारेषु च दत्त्वा अस्य आलेखस्य सर्वे शिखराः सम्बद्धाः सन्ति वा इति निर्धारयन्तु ।

【निवेश प्रारूप】
इनपुट् मध्ये अनेकाः दत्तांशसमूहाः सन्ति ।
प्रत्येकस्य दत्तांशसमूहस्य प्रथमपङ्क्तौ n, m च पूर्णाङ्कद्वयं भवति, यत् अनिर्देशितस्य आलेखस्य बिन्दुसङ्ख्यां किनारेषु च प्रतिनिधियति ।
अग्रिमाः m रेखाः, प्रत्येकं रेखायां x, y इति पूर्णाङ्कद्वयं भवति, यत् सूचयति यत् x बिन्दुः y बिन्दुः च सम्बद्धौ स्तः ।
बिन्दवः १ तः n पर्यन्तं सङ्ख्याः भवन्ति ।
चित्रे स्यात्द्विगुणधारातथास्व-पाशः。

[निर्गम प्रारूपम्] ।
प्रत्येकं दत्तांशसमूहः एकां रेखां एकं परिणामं च निर्गच्छति यदि सर्वे शिखराः संयोजिताः सन्ति तर्हि YES इति निर्गच्छति, अन्यथा NO इति निर्गच्छति ।

【दत्तांशपरिधि】
इनपुट् मध्ये १० पर्यन्तं दत्तांशसमूहाः सन्ति ।
१≤n≤१०००, २.
१≤मी≤५०००, २.
१≤x,y≤n

【इनपुट नमूना】
4 3
1 2
2 3
3 2
3 2
1 2
2 3

【निर्गम नमूना】
नहि
आम्‌

【एल्गोरिदम विश्लेषण】 .
● “ .संग्रहं च अन्वेष्टुम्"सङ्केतकार्यन्वयनविवरणार्थं कृपया पश्यन्तु:https://blog.csdn.net/hnjzsyjyj/लेख/विवरण/126455868
● अस्मिन् प्रश्ने संबद्धं आलेखं निर्धारयितुं dfs इत्यस्य उपयोगस्य सिद्धान्तः “dfs सम्बद्धस्य आलेखस्य सर्वान् बिन्दून् भ्रमितुं समर्थः भवितुमर्हति". यदि कश्चित् बिन्दुः न व्यतीतः तर्हि तस्य न संबद्ध इत्यर्थः।"

[एल्गोरिदम कोड: dfs + श्रृङ्खलाबद्ध अग्रे तारा]।
● dfs एल्गोरिदम टेम्पलेट:https://blog.csdn.net/hnjzsyjyj/लेख/विवरण/118736059
● श्रृङ्खला अग्रे ताराणां विषये विवरणार्थं कृपया पश्यन्तु :https://blog.csdn.net/hnjzsyjyj/लेख/विवरण/139369904

#include <bits/stdc++.h>
using namespace std;
 
const int N=1e3+5;
const int M=5e3+5;
int e[M<<1],ne[M<<1],h[N],idx;
bool st[N];
int n,m;
 
void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
void dfs(int u) {
    st[u]=1;
    for(int i=h[u]; i!=-1; i=ne[i]) {
        int j=e[i];
        if(!st[j]) dfs(j);
    }
}
 
int main() {
    while(cin>>n>>m) {
        memset(st,false,sizeof st);
        memset(h,-1,sizeof h);
        idx=0;
        while(m--) {
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }
 
        dfs(1);
 
        bool flag=true;
        for(int i=1; i<=n; i++)
            if(!st[i]) {
                flag=false;
                break;
            }
 
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
 
    return 0;
}
 
 
/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3
out:
NO
YES
*/

[एल्गोरिदम कोड: dfs + adjacency matrix]।
● dfs एल्गोरिदम टेम्पलेट:https://blog.csdn.net/hnjzsyjyj/लेख/विवरण/118736059
● अनिर्देशित अभारित आलेखस्य समीपता मैट्रिक्स कार्यान्वयनम् : १.https://blog.csdn.net/hnjzsyjyj/लेख/विवरण/116245897

#include <bits/stdc++.h>
using namespace std;
 
const int N=1010;
int g[N][N];
bool st[N];
int n,m;
 
void dfs(int u) {
    st[u]=true;
    for(int i=1; i<=n; i++)
        if(!st[i] && g[u][i]!=0) dfs(i);
}
 
int main() {
    while(cin>>n>>m) {
        memset(g,0,sizeof g);
        memset(st,false,sizeof st);
        int x,y;
        while(m--) {
            cin>>x>>y;
            g[x][y]=g[y][x]=1;
        }
        dfs(1);
        int i;
        for(i=1; i<=n; i++) {
            if(!st[i]) break;
        }
        if(i<=n) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}
 
/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3
out:
NO
YES
*/

【सन्दर्भाः】 २.
https://www.acwing.com/समाधान/सामग्री/124095/
https://blog.csdn.net/hnjzsyjyj/लेख/विवरण/118736059
https://blog.csdn.net/hnjzsyjyj/लेख/विवरण/139369904