Cod sursa(job #3335935)

Utilizator a_violetaAvram Violeta-Iulia a_violeta Data 23 ianuarie 2026 21:35:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.46 kb
//infoarena

/*
#include <iostream>
#include <vector>
#include <fstream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
ifstream fin("berarii2.in");
ofstream fout("berarii2.out");

void bfs(int nod, set<int>& solutie, vector<vector<int>>& adj_list, vector<int>& viz, vector<int>& dist) {
    queue<int> coada;
    coada.push(nod);
    viz[nod] = 1;
    solutie.insert(nod);//locatia berariei e accesibila pt berarie, da

    while (!coada.empty()) {
        int n = coada.front();
        coada.pop();
        for (auto vecin : adj_list[n]) {
            if (!viz[vecin]) {
                viz[vecin] = 1;
                solutie.insert(vecin);
                coada.push(vecin);
                if(dist[vecin] > dist[n] + 1)
                    dist[vecin] = dist[n] + 1;
            }
        }
    }
}

void dfs(int nod, set<int>& solutie, vector<vector<int>>& adj_list, vector<int>& viz) {

    viz[nod] = 1;
    solutie.insert(nod);

    for (auto vecin : adj_list[nod]) {
        if (!viz[vecin]) {
            dfs(vecin, solutie, adj_list, viz);
        }
    }
}

int main() {
    int n, m, p, x, y;
    fin >> n >> m >> p;

    vector<vector<int>> adj_list(n+1, vector<int>());
    vector<int> berarii(p+1);//in mod interesant, daca nu ii spun dimensiunea e vector out of range
    set<int> solutie;
    vector<int> viz(n+1, 0);
    vector<int> dist(n + 1, 100000);

    for (int i = 0; i < m; i++) {
        fin >> x >> y;
        adj_list[y].push_back(x);//e ordonat graful, l am si inversat acum
    }
    for (int i = 1; i <= p; i++) {
        fin >> x;
        berarii[i] = x;
        dist[x] = 0;
    }

    for (int i = 1; i <= p; i++) {
        
        for (int j = 1; j <= n; j++)
            viz[j] = 0;

        bfs(berarii[i], solutie, adj_list, viz, dist);
    }

    for (int i = 1; i <= n; i++) {
        cout << i << " " << dist[i] << "\n";
    }

    //vector<int> inaccesibile;

    //for (int i = 1; i <= n; i++) {

    //    if (solutie.find(i) == solutie.end()) {
    //        inaccesibile.push_back(i);
    //        cout << inaccesibile.back() << " ";
    //    }
    //}

    //cout << "\n";

    //sort(inaccesibile.begin(), inaccesibile.end());

    //fout << inaccesibile.size() << "\n";
    //for (auto i : inaccesibile) {
    //    fout << i << "\n";
    //}

    return 0;
}

*/

//tare conexe: 2 parcurgeri dfs, pe graful normal si pe graful transpus
//ordonam descrescator dupa timpul de iesire
//kosaraju
//O(n+m)

//obs.: graful componentelor tare conexe musai nu are ciclu

#include <iostream>
#include<fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

void dfs1(int nod, vector<int>& viz, vector<vector<int>>& adj_list, stack<int>& stiva) {
    viz[nod] = 1;
    for (auto vecin : adj_list[nod]) {
        if (!viz[vecin]) {
            dfs1(vecin, viz, adj_list, stiva);
        }
    }
    stiva.push(nod);
}

void dfs2(int nod, vector<int>& viz, vector<vector<int>>& adj_list, vector<vector<int>>& ctc, int nr) {
    viz[nod] = 1;
    ctc[nr].push_back(nod);
    for (auto vecin : adj_list[nod]) {
        if (!viz[vecin]) {
            dfs2(vecin, viz, adj_list, ctc, nr);
        }
    }
}

int main() {

    int n, m, x, y, start;
    fin >> n >> m;

    vector<vector<int>> adj_list(n + 1, vector<int>());
    vector<vector<int>> adj_list_t(n + 1, vector<int>());
    stack<int> stiva;
    vector<int> viz(n + 1, 0);
    vector<vector<int>> ctc(n+1, vector<int>());

    for (int i = 1; i <= m; i++) {
        fin >> x >> y;
        adj_list[x].push_back(y);
        adj_list_t[y].push_back(x);//transpus

        //if (i == 1) start = x;
    }

    for (int i = 1; i <= n; i++) {
        if (!viz[i])
            dfs1(i, viz, adj_list, stiva);
    }

    for (int i = 1; i <= n; i++) {
        viz[i] = 0;
    }

    int nr = 0;
    while (!stiva.empty()) {
        start = stiva.top();
        stiva.pop();
        if (!viz[start]) {
            nr++;
            dfs2(start, viz, adj_list_t, ctc, nr);
        }
        
    }

    /*for (int i = 1; i < ctc.size(); i++) {
        if (!ctc[i].empty())
            nr++;
    }*/

    fout << nr << "\n";

    for (int i = 1; i <= nr; i++) {
        //cout << i << ": ";
        for (auto j : ctc[i]) {
            fout << j << " ";
        }
        fout << "\n";
    }

    return 0;
}

//codul pe infoarena ctc:

/*
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1e5;
vector<int> G[NMAX + 1];
vector<int> GT[NMAX + 1];
vector<int> ctc[NMAX + 1];
int vis1[NMAX + 1], vis2[NMAX + 1], nr;
vector<int> v;

void dfs1(int node) {
    vis1[node] = 1;
    for(int vecin : G[node]) {
        if(!vis1[vecin]) {
            dfs1(vecin);
        }
    }
    v.push_back(node);
}

void dfs2(int node) {
    vis2[node] = 1;
    ctc[nr].push_back(node);
    for(int vecin : GT[node]) {
        if(!vis2[vecin]) {
            dfs2(vecin);
        }
    }
}

int main() {
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
	int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) {
        if(!vis1[i]) {
            dfs1(i);
        }
    }
    for(int i = v.size() - 1; i >= 0; i--) {
        if(!vis2[v[i]]) {
            nr++;
            dfs2(v[i]);
        }
    }
    cout << nr << '\n';
    for(int i = 1; i <= nr; i++) {
        for(int x : ctc[i]) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}
*/

/*
#include <iostream>
#include <vector>
#include <>

using namespace std;

void dfs1(int node) {
	vis1[node] = 1;
	for (int vecin : G[node]) {
		if (!viz[vecin]) {
			dfs1(vecin);
		}
	}
	v.push_back(node);
}

void dfs2(int node) {
	vis2[node] = 1;
	ctc[nr].push_back(node);
	for (int vecin : GT[node]) {
		if (!viz2[vecin]) {
			dfs2(vecin);
		}
	}
	v.push_back(node);
}

int main() {

	int n, m;
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}
	for (int i = 1; i < n; i++) {
		if (!viz[i])
			dfs1(i);
	}

	for (int i = v.size() - 1; i >= 0; i--) {
		if (!viz2[v[i]) {
			nr++;
			dfs2(v[i]);
		}
	}
	for(int i)

	return 0;
}
*/