Mai intai trebuie sa te autentifici.

Cod sursa(job #2477164)

Utilizator rd211Dinucu David rd211 Data 19 octombrie 2019 18:47:01
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ofstream fout("ctc.out");
const int NMAX = 100010;
vector<int> graf[NMAX];
vector<int> grafInv[NMAX];

int viz[NMAX];
int vizPlus[NMAX],vizMinus[NMAX];
vector<vector<int>> comps;
int currentNode = 1;
int n,m;
void dfsPlus(int node)
{
    for(int i = 0; i<graf[node].size(); i++)
    {
        if(vizPlus[graf[node][i]]!=currentNode&&!viz[graf[node][i]])
        {
            vizPlus[graf[node][i]] = currentNode;
            dfsPlus(graf[node][i]);
        }
    }
}
void dfsMinus(int node)
{
    for(int i = 0; i<grafInv[node].size(); i++)
    {
        if(vizMinus[grafInv[node][i]]!=currentNode&&!viz[grafInv[node][i]])
        {
            if(vizPlus[grafInv[node][i]]==currentNode)
            {
                comps[comps.size()-1].push_back(grafInv[node][i]);
                viz[grafInv[node][i]] = true;
            }
            vizMinus[grafInv[node][i]]=currentNode;
            dfsMinus(grafInv[node][i]);
        }
    }
}
void getComp(int node)
{
    viz[node]=true;
    vector<int> v;
    v.push_back(node);
    comps.push_back(v);
    vizPlus[node]=currentNode;
    dfsPlus(node);
    vizMinus[node]=currentNode;
    dfsMinus(node);
}


class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
int main()
{
    ios::sync_with_stdio(0);
    InParser fin("ctc.in");
    fin>>n>>m;
    for(int i = 0; i<m; i++)
    {
        int x,y;
        fin>>x>>y;
        graf[x].push_back(y);
        grafInv[y].push_back(x);
    }
    for(; currentNode<=n; currentNode++)
    {
        if(!viz[currentNode])
        {
            getComp(currentNode);
        }
    }
    fout<<comps.size()<<'\n';
    for(int j = 0;j<comps.size();j++)
    {
        for(int i = 0;i<comps[j].size();i++)
            fout<<comps[j][i]<<" ";
        fout<<'\n';
    }
    return 0;
}