Pagini recente » Cod sursa (job #690652) | Cod sursa (job #882931) | Cod sursa (job #2139216) | Cod sursa (job #1960094) | Cod sursa (job #2816185)
#include <bits/stdc++.h>
using namespace std;
/**
Componente tare conexe (Strong connected)
Un digraf este tare conex daca exista drum intre oricare
doua noduri.
*/
vector<int> h[100003]; /// liste ad.
vector<int> g[100003]; /// liste ad. pe arce inverse
vector<int> ctc[100003]; /// componentele tare conexe
int n, m, nrc;
int st[100003], top;
int viz[100003];
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void Citire()
{
int i, j;
fin >> n >> m;
for (int k = 1; k <= m; k++)
{
fin >> i >> j;
h[i].push_back(j);
g[j].push_back(i);
}
}
void DFSF(int k)
{
viz[k] = 1;
for (int i : h[k])
if (viz[i] == 0) DFSF(i);
st[++top] = k;
}
/// Acum viz[i]=1 inseamna nevizitat si
/// viz[i]=0 inseamna vizitat
void DFS(int k)
{
viz[k] = 0;
for (int i : g[k])
if (viz[i] == 1) DFS(i);
ctc[nrc].push_back(k);
}
void ConstrCTC()
{
int i;
/// sortare topologica
for (i = 1; i <= n; i++)
if (viz[i] == 0)
DFSF(i);
/// determinare c.t.c
for (i = n; i >= 1; i--)
if (viz[st[i]] == 1)
{
nrc++;
DFS(st[i]);
}
}
void Afisare()
{
fout << nrc << "\n";
for (int i = 1; i <= nrc; i++)
{
///sort(ctc[i].begin, ctc[i].end());
for (int j : ctc[i])
fout << j << " ";
fout << "\n";
}
}
int main()
{
Citire();
ConstrCTC();
Afisare();
fin.close();
fout.close();
return 0;
}