Pagini recente » Cod sursa (job #477185) | Cod sursa (job #2325802) | Cod sursa (job #1671412) | Cod sursa (job #2401243) | Cod sursa (job #2939503)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void dfs_org(int);
void dfs_trn(int);
vector <int> v[100005], t[100005], dv, ctr[100005];
int ct[100005], f[100005];
int dfss, ctc, n, m;
int main()
{
int i, a, b;
fin>>n>>m;
for(i=1; i<=m; i++)
{
fin>>a>>b;
v[a].push_back(b);
t[b].push_back(a);
}
for(i=1; i<=n; i++)
{
if(ct[i]==0)
{
if(dv.size())
{
dv.clear();
}
dfss++;
dfs_org(i);
for(int j=int(dv.size())-1; j>=0; j--) //merg invers in vectorul format in dfs_org
{
if(f[dv[j]]==dfss && ct[dv[j]]==0) //daca nu are comp. tare con. , ii gasesc
{
//fout << '\n';
ctc++;
dfs_trn(dv[j]);
}
}
}
}
fout<<ctc<<'\n';
for(i=1; i<=ctc; i++)
{
sort(ctr[i].begin(), ctr[i].end());
for(auto j:ctr[i]) fout<<j<<' ';
fout<<'\n';
}
return 0;
}
//ma duc in toate nodurile posibile si le marchez ca vizitate
void dfs_org(int nod)
{
//fout<<nod<<' ';
f[nod]=dfss;
for(auto i:v[nod])
{
if(f[i]==0 && ct[i]==0)
{
dfs_org(i);
}
}
dv.push_back(nod);
}
//ma duc prin toate nodurile posibile din graful transpus si daca sunt vizitate in ambele parcurgeri, atunci sunt comp tare conexa comuna
void dfs_trn(int nod)
{
//fout<<nod<<' ';
ct[nod]=ctc;
ctr[ctc].push_back(nod);
for(auto i:t[nod])
{
if(f[i]==dfss && ct[i]==0)
{
dfs_trn(i);
}
}
}