Pagini recente » Cod sursa (job #1816961) | Cod sursa (job #2334982) | Cod sursa (job #467731) | Cod sursa (job #960941) | Cod sursa (job #2796192)
#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
unordered_map<int,bool> vizitat;
unordered_map<int,bool> vizitat2;
vector <int> S; ///stiva goala
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 <<" ";
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,ct=0;
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;
return 0;
}