Pagini recente » Profil flo | Cod sursa (job #649450) | Cod sursa (job #1865908) | Cod sursa (job #1287112) | Cod sursa (job #2526745)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100005;
int N, M, a, b, NrCTC;
int checked[NMAX];
stack< int > S;
vector< int >G[NMAX], //Graful propriu-zis
GT[NMAX], //Transpusa grafului
CTC[NMAX]; //Componentele tare conexe
void DFS1(int node)
{
checked[node] = 1;
for(size_t i = 0; i < G[node].size(); ++i) {
int next = G[node][i];
if(!checked[next])
DFS1(next);
}
S.push(node);
}
void DFS2(int node)
{
checked[node] = 2;
CTC[NrCTC].push_back(node);
for(size_t i = 0; i < GT[node].size(); ++i) {
int next = GT[node][i];
if(checked[next] == 1)
DFS2(next);
}
}
void Solution()
{
for(int i = 1; i <= N; ++i)
if(!checked[i])
DFS1(i);
while(!S.empty()) {
int Node = S.top();
if(checked[Node] == 1) {
NrCTC++;
DFS2(Node);
}
S.pop();
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fin >> N >> M;
for(int i = 0; i < M; i++) {
fin >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
Solution();
fout << NrCTC << "\n";
for(int i = 1; i <= NrCTC; ++i) {
for(size_t j = 0; j < CTC[i].size(); ++j)
fout << CTC[i][j] << " ";
fout << "\n";
}
}