Mai intai trebuie sa te autentifici.
Cod sursa(job #2568876)
Utilizator | Data | 4 martie 2020 10:16:34 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.07 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector < vector <int> > G, Gt;
vector <int> s, viz;
int nr;
void Dfs2(int x)
{
viz[x] = nr;
for(int i=0; i<Gt[x].size(); i++)
if(viz[ Gt[x][i] ] == -1)
Dfs2(Gt[x][i]);
}
void Dfs1(int x)
{
viz[x] = -1;
for(int i=0; i<G[x].size(); i++)
if(viz[ G[x][i] ] == 0)
Dfs1(G[x][i]);
s.push_back(x);
}
int main()
{
int n, m, x, y;
fin>>n>>m;
G.resize(n+1); Gt.resize(n+1); viz.resize(n+1);
while(m)
{
fin>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
m--;
}
for(int i=1; i<=n; i++)
if(viz[i] == 0)
Dfs1(i);
for(int i=s.size()-1; i>=0; i--)
if(viz[s[i]] == -1)
{
nr++;
Dfs2(s[i]);
}
fout<<nr<<"\n";
for(int i=1; i<=nr; i++)
{
for(int j=1; j<=n; j++)
if(viz[j] == i)
fout<<j<<" ";
fout<<"\n";
}
return 0;
}