Pagini recente » Cod sursa (job #3304880) | Cod sursa (job #177524) | Cod sursa (job #362243) | Cod sursa (job #1016834) | Cod sursa (job #3326922)
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#define NMAX 100002
using namespace std;
int n, m, nrCTC;
bool vizitat[NMAX];
vector<vector<int>> Graf;
vector<vector<int>> GrafT;
stack<int> stiva;
vector<vector<int>> compTC;
void DFS1(int nod);
void DFS2(int nod);
void sortall();
void vectorswap(int first, int second);
int main()
{
int i, j, x, y;
//citire si graf transpus pentru CTC
cin>>n>>m;
Graf.resize(n + 2); GrafT.resize(n + 2); compTC.resize(n + 2);
for(i = 1; i <= m; i++)
{
cin>>x>>y;
Graf[x].push_back(y);
GrafT[y].push_back(x);
}
for(i = 1; i <= n; i++) //umplem stiva, primul DFS
if(!vizitat[i])
DFS1(i);
for(i = 1; i <= n; i++) vizitat[i] = 0;
while(stiva.size())
{
x = stiva.top(); stiva.pop();
if(!vizitat[x])
{
nrCTC++;
DFS2(x);
}
}
cout<<nrCTC<<'\n';
sortall();
for(i = 0; i < compTC.size(); i++)
if(compTC[i].size() > 0)
{
for(j = 0; j < compTC[i].size(); j++)
cout<<compTC[i][j]<<' ';
cout<<'\n';
}
return 0;
}
void sortall()
{
int i;
for(i = 0; i < compTC.size(); i++)
sort(compTC[i].begin(), compTC[i].end());
//bubblesort pt primul element al fiecarei comp conexe
bool sch = 0;
do
{
sch = 0;
for(i = 1; i < compTC.size(); i++)
if (compTC[i - 1].empty() || compTC[i].empty())
continue;
else
if(compTC[i - 1][0] > compTC[i][0])
{
//swap la cei doi vectori
vectorswap(i - 1, i);
sch = 1;
}
}
while(sch);
}
void vectorswap(int first, int second)
{
int i;
vector<int> aux;
for(i = 0; i < compTC[first].size(); i++) aux.push_back(compTC[first][i]); //mut primul in aux
compTC[first].resize(compTC[second].size());
for(i = 0; i < compTC[second].size(); i++) compTC[first][i] = compTC[second][i]; //mut al doilea in primul
compTC[second].resize(aux.size());
for(i = 0; i < aux.size(); i++) compTC[second][i] = aux[i]; //mut aux (primul) in al doilea
}
void DFS2(int nod)
{
vizitat[nod] = 1;
for(int i = 0; i < GrafT[nod].size(); i++)
if(!vizitat[GrafT[nod][i]])
{
DFS2(GrafT[nod][i]);
}
compTC[nrCTC].push_back(nod);
}
void DFS1(int nod)
{
vizitat[nod] = 1;
for(int i = 0; i < Graf[nod].size(); i++)
if(!vizitat[Graf[nod][i]])
{
DFS1(Graf[nod][i]);
}
stiva.push(nod);
}