Pagini recente » Cod sursa (job #877763) | Cod sursa (job #461836) | Cod sursa (job #1895558) | Cod sursa (job #252202) | Cod sursa (job #1519410)
// storngly linked(connected) verticles - componente tare conexe
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
using VI = vector<int>;
int n, m, nrc;
vector<VI> G1, G2, C;
vector<bool> s;
stack<int> st;
void Read();
void Df1(int x);
void Df2(int x);
int main()
{
Read();
for ( int i = 1; i <= n; i++ )
if ( !s[i] )
Df1(1);
s.assign(n+1, 0);
int x;
while (!st.empty())
{
x = st.top();
st.pop();
if ( s[x] != 1 )
{
nrc++;
Df2(x);
}
}
fout << nrc << '\n';
for ( int i = 1; i <= nrc; i++ )
{
for ( const int& y : C[i] )
fout << y << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> n >> m;
G1 = vector<VI>(n+1);
G2 = vector<VI>(n+1);
C = vector<VI>(n+1);
s = vector<bool>(n+1);
int x, y;
for ( int i = 1; i <= m; i++ )
{
fin >> x >> y;
G1[x].push_back(y);
G2[y].push_back(x);
}
}
void Df1(int x)
{
s[x] = 1;
for ( const int& y : G1[x] )
{
if ( s[y] != 1 )
Df1(y);
}
st.push(x);
}
void Df2(int x)
{
s[x] = 1;
C[nrc].push_back(x);
for ( const int& y : G2[x] )
{
if ( s[y] != 1 )
Df2(y);
}
}