Pagini recente » Cod sursa (job #1343443) | Cod sursa (job #1576478) | Cod sursa (job #2215169) | Cod sursa (job #568263) | Cod sursa (job #2796319)
#include<bits/stdc++.h>
using namespace std;
///CTC Kosaraju
ifstream in ("ctc.in");
ofstream out ("ctc.out");
vector<int> la[100005]; ///lista de adiacenta
vector<int> lat[100005]; ///lista de adiacenta pt graful transpus
bool vizitat[100005];
bool vizitat2[100005];
//unordered_map<int,bool> vizitat3;
vector <int> c[100005]; ///componentele tare conexe
vector <int> S; ///stiva goala
int ct;
void DFS1(int nod)
{
vizitat[nod] = true; ///marcam nodul ca vizitat
for (int i = 0; i < la[nod].size(); i++) ///parcurgem lista de adiacenta a nodului curent
if (!vizitat[la[nod][i]]) ///cand gasim un nod nevizitat , continuam dfs prin el
{
DFS1(la[nod][i]);
}
S.push_back(nod);
}
void DFS2(int nod)
{
vizitat2[nod] = true; ///marcam nodul ca vizitat
//out<< nod <<" ";
c[ct].push_back(nod);
for (int i = 0; i < lat[nod].size(); i++) ///parcurgem lista de adiacenta a nodului curent
if (!vizitat2[lat[nod][i]]) ///cand gasim un nod nevizitat , continuam dfs prin el
{
DFS2(lat[nod][i]);
}
}
int main()
{
int n,m;
in>>n>>m; ///citim nr noduri + nr muchii
for(int i=1; i<=m; i++)
{
int a,b;
in>>a>>b;
///graf orientat
la[a].push_back(b);
lat[b].push_back(a);
}
for(int i = 1; i <= n; i++)
{
if(vizitat[i] == 0)
{
DFS1(i);
// ct++;
}
}
for( int i = S.size()-1 ;i >= 0 ; i--)
{
//out<<S[i]<<" ";
int v = S[i];
if(vizitat2[v] == 0)
{
DFS2(v);
//out<<'\n';
ct++;
}
}
out<<ct<<'\n';
for( int i = 0 ;i < ct ; i ++)
{
for(int j = 0; j < c[i].size(); j++)
out<<c[i][j]<<" ";
out<<'\n';
}
return 0;
}