Mai intai trebuie sa te autentifici.
Cod sursa(job #2477164)
Utilizator | 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;
}