Pagini recente » Cod sursa (job #1373159) | Cod sursa (job #1120420) | Cod sursa (job #2533715) | Cod sursa (job #1445746) | Cod sursa (job #3270925)
#include <bits/stdc++.h>
using namespace std;
vector <int> v1[100001], v2[100001], ctc[100001];
int verif[100001];
int st[100001];
int cnt, cnt2;
void dfs1(int nod)
{
verif[nod] = 1;
for(auto y:v1[nod])
{
if(verif[y] == 0) dfs1(y); ///mergem recursiv prin nodurile nevizitate
}
st[cnt] = nod;
cnt++;
}
void dfs2(int nod)
{
verif[nod] = 1;
ctc[cnt2].push_back(nod);
for(auto y:v2[nod])
{
if(verif[y] == 0) dfs2(y);
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
f >> n >> m;
for(int i = 1; i <= m; i ++)
{
int a, b;
f >> a >> b;
v1[a].push_back(b);
v2[b].push_back(a);
}
for(int i = 1; i <= n; i ++)
{
if(verif[i] == 0) dfs1(i);
}
for(int i = 1; i <= n; i ++)
verif[i] = 0;
for(int i = cnt - 1; i >= 0; i --)
{
int x = st[i];
if(verif[x] == 0)
{
dfs2(x);
cnt2 ++;
}
}
g << cnt2 << '\n';
for(int i = 0; i < cnt; i ++)
{
for(auto it : ctc[i])
g << it << " ";
g << '\n';
}
return 0;
}