Pagini recente » Cod sursa (job #1642967) | Cod sursa (job #1535474) | Cod sursa (job #2285391) | Cod sursa (job #1283204) | Cod sursa (job #2928985)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
vector<int> G[100002],T[100002],C[100002];
int N, M, nr, x, y, vizitat[100002];
stack<int> stiva;
void dfs(int Nod) //dfs pe nodurile grafului
{
vizitat[Nod] = 1;
for( int i=0; i<G[Nod].size();i++) {
if(vizitat[G[Nod][i]] == 0)
dfs(G[Nod][i]);
}
stiva.push(Nod); //punem nodurile pe stiva, pentru a putea retine ordinea inversa
}
void dfs_2(int Nod) //dfs pe nodurile transpusei
{
vizitat[Nod] = 2;
for(int i=0; i < T[Nod].size(); i++) {
if(vizitat[T[Nod][i]] == 1)
dfs_2(T[Nod][i]);
}
C[nr].push_back(Nod); //adaugam nodul la componenta conexa
}
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int main()
{
fin >> N >> M;
for(int i = 1; i <= M; i++)
{
//construim graful si transpusa garfului
fin >> x >> y;
G[x].push_back(y);
T[y].push_back(x);
}
for(int i=1;i<=N;i++)
if(vizitat[i] == 0)
dfs(i); //apelam dfs pt nodurile grafului
while(stiva.empty()==0) {
//scoatem cate un nod de pe stiva, obtinand astfel ordinea inversa a acestora
if (vizitat[stiva.top()] == 1) {
nr++; //creste nr-ul de componente conexe
dfs_2(stiva.top());
}
stiva.pop();
}
fout << nr << "\n";
for(int i = 1; i <= nr; i++) {
for(int j = 0; j < C[i].size(); j++)
fout << C[i][j] << " ";
fout<<"\n";
}
return 0;
}