Cod sursa(job #3148906)

Utilizator Carol7237Stanciu Carol Carol7237 Data 5 septembrie 2023 02:35:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.96 kb
//We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people,
//and they should not go into the same group.
//Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi,
//return true if it is possible to split everyone into two groups in this way.
// Mai pe scurt acesta este un BFS putin diferit
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 2001;
//int n, m;
//bool isBipartite;
//int adj[MAX][MAX], viz[MAX];
//queue<int> q;
//
//void BFS(){
//    q.push(1);
//    viz[1] = 1;
//    while(!q.empty()){
//        int aux = q.front();
//        q.pop();
//        for(int i = 1; i <= n; i++){
//            if(viz[aux] == viz[i] && adj[aux][i] == 1){
//                isBipartite = false;
//                return;
//            }
//            else if(adj[aux][i] == 1 && viz[i] == 0){
//                q.push(i);
//                if(viz[aux] == 1){
//                    viz[i] = 2;
//                }
//                else{
//                    viz[i] = 1;
//                }
//            }
//        }
//    }
//}
//
//int main() {
//
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        adj[x][y] = adj[y][x] = 1;
//    }
//    isBipartite = true;
//    BFS();
//    if(!isBipartite){
//        fout << "False" << endl;
//    }
//    else{
//        fout << "True" << endl;
//        for(int i = 1; i <= n; i++){
//            if(viz[i] == 1){
//                fout << i << ' ';
//            }
//        }
//        fout<<endl;
//        for(int i = 1; i <= n; i++){
//            if(viz[i] == 2){
//                fout << i << ' ';
//            }
//        }
//        fout<<endl;
//    }
//
//    return 0;
//}
//

//One of the most popular algorithms for traversing a graph is the Depth First Search (DFS).
//The DFS is usually implemented as a recursive function. First we call the function for the starting node.
//For each call, we go through the adjacency list of the current node, and recursively call the function for the unvisited neighbours.
//Notice that if we permute the adjacency lists of the nodes, the order in which we visit them might differ.
//In this problem you are given a graph with N nodes and M edges and a permutation P of size N.
//If you are allowed to shuffle the adjacency lists, is it possible to visit the nodes during a DFS starting in node
//1 in the order given by P?
//Mai pe scurt acesta este un DFS care are o sortare in fiecare lista de adiacenta!
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 1e5 + 3;
//int n, m;
//vector<int> adj[MAX], dfs_order;
//int ord[MAX], viz[MAX];
//
//
//int compara(int a, int b){
//    return ord[a] < ord[b];
//}
//
//void DFS(int node){
//    viz[node] = 1;
//    dfs_order.push_back(node);
//    for(auto vecin : adj[node]){
//        if(viz[vecin] == 0){
//            DFS(vecin);
//        }
//    }
//}
//
//int main() {
//
//    fin >> n >> m;
//    vector<int> permutare(n);
//    for(int i = 1; i <= n; i++){
//        int aux;
//        fin >> aux;
//        ord[aux] = i;
//        permutare[i - 1] = aux;
//    }
//
//
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        adj[x].push_back(y);
//        adj[y].push_back(x);
//    }
//    for(int i = 1; i <= n; i++){
//        sort(adj[i].begin(), adj[i].end(), compara);
//    }
//
//    DFS(1);
// //    fout << "dfs_order : " << endl;
// //    for(int i = 0; i < n ; i++){
// //        fout << dfs_order[i] << ' ';
// //    }
// //    fout << endl << "permutare : \n";
// //    for(int i = 0; i < n; i++){
// //        fout << permutare[i] << ' ';
// //    }
//    fout << (permutare == dfs_order) << endl;
//
//    return 0;
//}

//There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where
//prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
//For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
//Return the ordering of courses you should take to finish all courses. If there are many valid answers,
//return any of them. If it is impossible to finish all courses, return an empty array.
//
//Problema cu cursurile adica un graf orientat in care trebuie sa aflam daca avem ciclu sau nu. Nu e terminata aici.


//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//const int MAX = 1e4 + 1;
//int n, m;
//vector<int> adj[MAX], viz, cur_path, rezultat;
//vector<int> DFS(int node){
//
//    if(viz[node]){
//        return {};
//    }
//    if(cur_path[node]){
//        return {node};
//    }
//
//    viz[node] = 1;
//    cur_path[node] = 1;
//    for(auto vecin : adj[node]){
//        vector<int> ciclu = DFS(vecin);
//        if(!ciclu.empty()){
//            return ciclu;
//        }
//    }
//    cur_path[node] = 0;
//    rezultat.push_back(node);
//    return {};
//}
//
//int main() {
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        adj[y].push_back(x);
//    }
//    int ans = 1;
//    for(int i = 1; i <= n; i++){
//        if(!viz[i]){
//            vector<int> ciclu = DFS(i);
//            if(!ciclu.empty()){
//                ans = 0;
//            }
//        }
//    }
//
//
//    return 0;
//}

#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int MAX = 1e5 + 1, NEVIZITAT = -1;

int n, m, id, sccCount, ids[MAX], low[MAX];
vector<int> adj[MAX], cur_path[MAX];
stack<int> stiva;
vector<bool> onStack(MAX, false);


void DFS(int node){

    onStack[node] = true;
    stiva.push(node);
    ids[node] = low[node] = id++;

    for(auto vecin : adj[node]){
        if(ids[vecin] == NEVIZITAT){
            DFS(vecin);
        }

        if(onStack[vecin]){
            low[node] = min(low[node], low[vecin]);
        }
    }

    if(low[node] == ids[node]){
        while(!stiva.empty()){
            int aux = stiva.top();
            stiva.pop();
            cur_path[sccCount].push_back(aux);
            onStack[aux] = false;
            low[aux] = ids[node];
            if(aux == node){
                break;
            }
        }
        sccCount++;
    }


}


int main() {

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
    }

    for(int i = 1; i <= n; i++){
        ids[i] = NEVIZITAT;
    }

    for(int i = 1; i <= n; i++){
        if(ids[i] == NEVIZITAT){
            DFS(i);
        }
    }

    fout << sccCount << endl;
    for(int i = 0 ; i < sccCount; i++){
        for(auto cmp : cur_path[i]){
            fout << cmp << ' ';
        }
        fout << endl;
    }
    return 0;
}